I came across a problem:
Given an array, find the max count of this array, where count for an element in the array is defined as the no. of elements from this array which can divide this element.
Example: max count from the array [2,2,2,5,6,8,9,9] is 4 as 6 or 8 can be divided by 2,2,2 and by themselves.
My approach is:
- Sort the array.
- Make a set from this array (in a way such that even this set is sorted in non-descending order).
- Take another array in which the array indices are initialized to the no. of times an element appears in the original array. Example: in above example element '2' comes three times, hence index '2-1' in this new array will be initialized to 3, index '9-1' will be initialized to 2 as '9' comes 2 times in this array.
- Using two loops I am checking the divisibility of largest (moving largest to smallest) element in the set with smallest (moving smallest to largest) element of the set.
Conditions
1 <= arr[i] <= 10000
1 <= i <= 10000
#include <stdio.h>
#include <stdlib.h>
#include<limits.h>
int cmp(const void *a, const void *b)
{
return (*(int*)a - *(int*)b);
}
void arr_2_set(int *arr, int arr_size,int *set, int *len)
{
int index = 0;
int set_len = 0;
int ele = INT_MIN;
qsort(arr,arr_size,sizeof(int),cmp);
while(index < arr_size)
{
if(ele != arr[index])
{
ele = arr[index];
set[set_len] = ele;
set_len ;
}
index ;
}
*len = set_len;
}
int main(void)
{
int arr[]={2,2,2,5,6,8,9,9}; //array is already sorted in this case
int size = sizeof(arr)/sizeof(arr[0]);
int set[size];
int index = 0;
int set_len = 0;
arr_2_set(arr, size, set, &set_len); //convert array to set - "set_len" is actual length of set
int rev = set_len-1; //this will point to the largest element of set and move towards smaller element
int a[100000] = {[0 ... 99999] = 0}; //new array for keeping the count
while(index<size)
{
a[arr[index] -1] ;
index ;
}
int half;
int max=INT_MIN;
printf("set len =%d\n\n",set_len);
for(;rev>=0;rev--)
{
index = 0;
half = set[rev]/2;
while(set[index] <= half)
{
if(set[rev]%set[index] == 0)
{
a[set[rev] -1] = a[set[index]-1]; //if there are 3 twos, then 3 should be added to count of 8
//printf("index =%d rev =%d set[index] =%d set[rev] =%d count = %d\n",index,rev,set[index],set[rev],a[set[rev] -1]);
}
if(max < a[set[rev]-1])
max = a[set[rev]-1];
index ;
}
}
printf("%d",max);
return 0;
}
Now my question is how can I speed up this program? I was able to pass 9/10 test cases - for the 10th test case (which was hidden), it was showing "Time Limit Exceeded".
CodePudding user response：
- For creating a set and finding the count - use a single
whileloop, when the size of array is big then using a single loop will matter a lot. - In the later half section where two nested loops are there - don't go from largest to smallest element. Go from smallest to largest element while checking which largest element with index lower than the current element can divide this element, add the count of that element to the current element's count (using
set[i]/2logic will still hold here). This way you'll avoid a lot of divisions. Example: if set is{2,3,4,8}in this case, lets say your current position is8then you go down till largest element smaller than or equal to8which can divide8and add it's count to current element's (8) count.
CodePudding user response：
[Edit]
Post to be taken down later. Needs too much rework.
At least these issues:
Bad compare
*(int*)a - *(int*)b risks overflow leading to wrong answers/undefined behavior.
(*(int*)a > *(int*)b) - (*(int*)a < *(int*)b) does not.
Fewer iterations
Rather than iterate to 1/2 of set[rev], iterate to the square root of set[rev]. That is set[index]*set[index]) <= set[rev]. Yet avoid that form as set[index]*set[index] <= set[rev] may overflow.
// while(set[index] <= half)
while(set[index] <= set[rev]/set[index])
A good compiler will see the set[rev]/set[index] and nearby set[rev]%set[index] and emit efficient code for the time price of
one.
Makes a big difference when size is large. O() goes from 0(n*n) to O(n*sqrt(n)) time.
For such time limited tasks, seek to reduce the Big O notation. Do not bother with linear improvements like making the code twice as fast.
Zero ?
Hopefully, no element is zero.
CodePudding user response：
for the 10th test case (which was hidden), it was showing "Time Limit Exceeded".
That may suggest a more time efficient algorithm is expected.
The posted one, first sorts the array (using qsort) and then copies only the unique values into another array, set.
Given the constraints on the possible values, it may be cheaper to implement a counting sort algorithm.
The last part, which searches the maximum number of dividends, can then be implemented as a sieve, using an additional array.
#include <stdio.h>
enum constraints {
MAX_VALUE = 10000
};
int count_dividends(size_t n, int const *arr)
{
// The actual maximum value in the array will be used as a limit.
int maxv = 0;
int counts[MAX_VALUE 1] = {0};
for (size_t i = 0; i < n; i)
{
if ( counts[arr[i]] == 0 && arr[i] > maxv )
{
maxv = arr[i];
}
counts[arr[i]];
}
// Now, instead of searching for the dividends of an element, it
// adds the number of factors to each multiple.
// So, say there are two elements of value 3, it adds 2 to all
// the multiples of 3 in the total array.
int totals[MAX_VALUE 1] = {0};
int count = 0;
// It starts from 2, it will add the numbers of 1's once, at the end.
for (int i = 2; i <= maxv; i)
{
// It always skips the values that weren't in the original array.
if ( counts[i] != 0 )
{
for ( int j = 2 * i; j <= maxv; j = i)
{
if ( counts[j] != 0 )
totals[j] = counts[i];
}
if ( counts[i] totals[i] > count )
{
count = counts[i] totals[i];
}
}
}
return count counts[1];
}
int main(void)
{
{
int a[] = {2, 4, 5, 1, 1, 6, 14, 8, 2, 12, 1, 13, 10, 2, 8, 5, 9, 1};
size_t n = (sizeof a) / (sizeof *a);
// Expected: 10, because of 1 1 1 1 2 2 2 4 8 8
printf("%d\n", count_dividends(n, a));
}
{
int a[] = {2, 4, 5, 2, 7, 10, 9, 8, 2, 4, 4, 6, 5, 8, 4, 7, 6};
size_t n = (sizeof a) / (sizeof *a);
// Expected: 9, because of 2 2 2 4 4 4 4 8 8
printf("%d\n", count_dividends(n, a));
}
}