#include <stdio.

h>
#include <string.h>
#include <stdlib.h>

int compare(const char **a, const char **b)

{
return strcmp(*a, *b);
}

char** mostActive(int customers_count, char** customers, int* result_count)

{
qsort(customers, customers_count, sizeof(char *), compare);

int size = 0;
char **arr = (char **)malloc(size * sizeof(char *));

int count = 1;
for (int i = 0; i < customers_count - 1; i++)
{
if (strcmp(customers[i], customers[i + 1]) == 0)
{
count++;
continue;
}

if (count >= customers_count * 0.05)

{
arr = (char **)realloc(arr, ++size * sizeof(char *));
arr[size - 1] = customers[i];
}
count = 1;
}

if (count >= customers_count * 0.05)

{
arr = (char **)realloc(arr, ++size * sizeof(char *));
arr[size - 1] = customers[customers_count - 1];
}

*result_count = size;
return arr;
}
#include <stdio.h>
#include <stdlib.h>

int mostBalancedPartition(int parent_count, int* parent, int files_size_count, int* files_size)

{

for (int i = parent_count - 1; i > 0; i--)

{
files_size[parent[i]] += files_size[i];
}

int mindiff = files_size[0];

int diff = mindiff;
for (int i = 1; i < files_size_count; i++)
{
diff = abs(files_size[0] - 2 * files_size[i]);
mindiff = (diff < mindiff) ? diff : mindiff;
}
return mindiff;
}
#include <stdio.h>
#include <stdlib.h>

int longestSubarray(int arr_count, int* arr)

{
int x, y, max;
x = y = max = 1;

for (int i = 1; i < arr_count; i++)

{
if (arr[i - 1] == arr[i])
{
x++;
y++;
}
else if (arr[i - 1] == (arr[i] - 1))
{
x = y + 1;
y = 1;
}
else if (arr[i - 1] == (arr[i] + 1))
{
y = x + 1;
x = 1;
}
else
{
x = y = 1;
};

max = (x > max) ? ((x > y) ? x : y) : ((max > y) ? max : y);

}

return max;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int maxCost(int cost_count, int* cost, int labels_count, char** labels, int dailyCount)
{
int maxcost = 0;
int sumcost = 0;
int count = 0;
for (int i = 0; i < labels_count; i++)
{
if (!strcmp(labels[i], "legal"))
{
count++;
}
sumcost += cost[i];
if (count == dailyCount)
{
maxcost = maxcost > sumcost ? maxcost : sumcost;
sumcost = 0;
count = 0;
}
}

return maxcost;
}
#include <stdio.h>
#include <stdlib.h>

// -------------------------------------- O(n log n) Using Quick sort ---------------------------------------------------//

long gcd(long a, long b) // Greatest Common Divisor Function

{
return b > 0 ? gcd(b, a % b) : a;
}

long compare(const long *a, const long *b) // Compare Function To Sort 2D Array
{
return (*a - *b) ? (*a - *b) : (*(a + 1) - *(b + 1));
};

long nearlySimilarRectangles(int sides_rows, int sides_columns, long **sides)

{
long arr[sides_rows][2];

for (int i = 0; i < sides_rows; i++)

{
long z = gcd(sides[i][0], sides[i][1]);
arr[i][0] = sides[i][0] / z;
arr[i][1] = sides[i][1] / z;
}

qsort(arr, sides_rows, sizeof(arr[0]), compare);

long count = 1;
long sum = 0;
long acc = 0;

for (int i = 0; i < sides_rows - 1; i++)

{
if (arr[i][0] == arr[i + 1][0] && arr[i][1] == arr[i + 1][1])
{
count++;
acc = ((count * (count - 1)) / 2); // n(n-1)/2
continue;
}
sum += acc;
count = 1;
acc = 0;
}
sum += acc;

return sum;
};
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
long compare(long *a, long *b)
{
return *b - *a;
}

long minTime(int files_count, int* files, int numCores, int limit)

{
long total = 0;
int n = 0;
long *max = (long *)calloc(n, sizeof(long));
for (int i = 0; i < files_count; i++)
{
if (!(files[i] % numCores))
{
max = (long *)realloc(max, ++n * sizeof(long));
max[n - 1] = files[i];
continue;
}
total += files[i];
}

qsort(max, n, sizeof(long), compare);

for (int i = 0; i < n; i++)

{
if (i < limit)
{
total += (max[i] / numCores);
}
else
{
total += max[i];
}
}
free(max);
return total;
}
char *decryptPassword(char *s)
{
int len = strlen(s);
int j = 0;
int x = 0;
char *newS = (char *)calloc(x, sizeof(char));
for (int i = 0; i < len; i++)
{
if (isdigit(s[i]) && s[i] != '0')
{
j++;
continue;
}
if ((i < len - 2) && s[i + 2] == '*')
{
x += 2;
newS = (char *)realloc(newS, x * sizeof(char));
newS[x - 2] = s[i + 1];
newS[x - 1] = s[i];
i += 2;
}
else if (s[i] == '0')
{

newS = (char *)realloc(newS, ++x * sizeof(char));

newS[x - 1] = s[j - 1];
j--;
}
else
{

newS = (char *)realloc(newS, ++x * sizeof(char));

newS[x - 1] = s[i];
}
}

newS = (char *)realloc(newS, ++x * sizeof(char));

newS[x-1]='\0';

return newS;
}
char * decryptPassword(char *s)
{
int len = strlen(s);
char temp;
int j = 0;
int i = 0;
int x = 0;
char *numbers = (char *)calloc(x, sizeof(char));
for (i; i < len; i++)
{
if (isdigit(s[i]) && s[i] != '0')
{
numbers = (char *)realloc(numbers, ++x * sizeof(char));
numbers[x - 1] = s[i];
j++;
continue;
}

if (s[i] == '*')
{

temp = s[i - j - 1];

s[i - j - 1] = s[i - j - 2];
s[i - j - 2] = temp;
j++;
}
else if (s[i] == '0')
{
s[i - j] = numbers[(x--) - 1];
}
else
{
s[i - j] = s[i];
}
}

{
s[i - j] = '\0';
}

free(numbers);
return s;
}
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int compare(int *a, int *b)
{
return *b - *a;
}
long getMinCost(int crew_id_count, int* crew_id, int job_id_count, int* job_id)
{
qsort(crew_id, crew_id_count, sizeof(int), compare);
qsort(job_id, job_id_count, sizeof(int), compare);

long totalDistance = 0;
for (int i = 0; i < crew_id_count; i++)
{

totalDistance += abs(crew_id[i] - job_id[i]);

}

return totalDistance;
}
#include <stdio.h>
#include <stdlib.h>
int compare(const char **a, const char **b)
{
return strcmp(*a, *b);
}

int compare_chars(const char *a, const char *b)

{

return *a - *b;
}
int binarySearchString(char **arr, int n, char target[]) //------------ log(n) ----------//
{
int low = 0;
int high = n - 1;
int count = 0;
int i = 0;
while (low <= high)
{

i++;
int mid = low + (high - low) / 2;
int cmp = strcmp(arr[mid], target);
if (cmp == 0)
{
count++;
int left = mid - 1;
int right = mid + 1;
while (left >= 0 && strcmp(arr[left], target) == 0)
{
count++;
left--;
}
while (right < n && strcmp(arr[right], target) == 0)
{
count++;
right++;
}
break;
}
if (cmp < 0)
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}

return count;
}
int* stringAnagram(int dictionary_count, char** dictionary, int query_count, char** query, int* result_count)
{
char **new_query = (char **)calloc(query_count, sizeof(char *));

for (int i = 0; i < query_count; i++)

{
int n = strlen(query[i]);
new_query[i] = (char *)calloc(n + 1, sizeof(char));
strcpy(new_query[i], query[i]);
qsort(new_query[i], n, sizeof(char), compare_chars); //------------ n log(n) ----------//
}

char **new_dec = (char **)calloc(dictionary_count, sizeof(char *));

for (int i = 0; i < dictionary_count; i++)
{
int n = strlen(dictionary[i]);
new_dec[i] = (char *)calloc(n + 1, sizeof(char));
strcpy(new_dec[i], dictionary[i]);
qsort(new_dec[i], n, sizeof(char), compare_chars); //------------ n log(n) ----------//
};

qsort(new_dec, dictionary_count, sizeof(char *), compare); //------------ n log(n) ----------//

int *ans = (int *)calloc(query_count, sizeof(int));

for (int i = 0; i < query_count; i++)
{
ans[i] = binarySearchString(new_dec, dictionary_count, new_query[i]); //------------ log(n) ----------//
}

*result_count = query_count;

return ans;
}
#include <stdio.h>
long* findSum(int numbers_count, int* numbers, int queries_rows, int queries_columns, int** queries, int*
result_count)
{

long *result = (long *)malloc(queries_rows * sizeof(long));

long a[numbers_count + 1];
long b[numbers_count + 1];
a[0] = 0;
b[0] = 0;

for (int i = 0; i < numbers_count; i++)

{
a[i + 1] = a[i] + numbers[i];
b[i + 1] = b[i] + (numbers[i] == 0);
}

for (int i = 0; i < queries_rows; i++)

{
int x = queries[i][2];
int r = queries[i][1];
int l = queries[i][0];

result[i] = a[r] - a[l - 1] + x * (b[r] - b[l - 1]);

}

*result_count=queries_rows;
return result;
}
#include <stdio.h>
int compare(int *a, int *b)
{
return *a - *b;
}

int filledOrders(int order_count, int* order, int k)

{

qsort(order, order_count, sizeof(int), compare);

int filled;
for (int i = 0; i < order_count; i++)
{
if (order[i] <= k)
{
filled++;
k -= order[i];
}
else
{
break;
}
}
return filled;
}
#include <stdio.h>
#include <string.h>

int compare_chars(const char *a, const char *b)

{

return *a - *b;
}

char** possibleChanges(int usernames_count, char** usernames, int* result_count)

{

char **result = (char *)malloc(usernames_count * sizeof(char *));

for (int i = 0; i < usernames_count; i++)

{
char *temp = (char *)calloc(strlen(usernames[i]) + 1, sizeof(char));
strcpy(temp, usernames[i]);
qsort(temp, strlen(temp), sizeof(char), compare_chars);
if (strcmp(usernames[i], temp))
{
result[i] = "YES";
}
else
{
result[i] = "NO";
}
free(temp);
}

*result_count=usernames_count;
return result;
}
#include <stdio.h>
#include <string.h>

char* findSubstring(char* s, int k)

{
char *result = (char *)malloc((k + 1) * sizeof(char));
char vowels[] = "aeiou";
int count = 0;
int ans = 0;
char *ptr;

for (int i = 0; i < k; i++)

{
ptr = strchr(vowels, s[i]);
count += (ptr != NULL);
}
int max = count;
for (int i = k; i < strlen(s); i++)
{
ptr = strchr(vowels, s[i]);
count += (ptr != NULL);
ptr = strchr(vowels, s[i - k]);
count -= (ptr != NULL);

if (count > max)

{
max = count;
ans = i - k + 1;
}
}

if (max > 0)
{
strncpy(result, s + ans, k);
result[k] = '\0';
return result;
}

free(result);
return "Not found!";
}
#include <stdio.h>
#include <string.h>

char* findSubstring(char* s, int k)

{
char *result = (char *)malloc((k + 1) * sizeof(char));
int key[256] = {};
char vowels[] = "aeiou";
for (int i = 0; i < strlen(vowels); i++)
{
key[vowels[i]] = 1;
}

int count = 0;
int ans = 0;

for (int i = 0; i < k; i++)

{
count += key[s[i]];
}
int max = count;
for (int i = k; i < strlen(s); i++)
{
count += key[s[i]];
count -= key[s[i - k]];

if (count > max)

{
max = count;
ans = i - k + 1;
}
}

if (max > 0)
{
strncpy(result, s + ans, k);
result[k] = '\0';
return result;
}

free(result);
return "Not found!";
}