Codility: MaxZeroProduct - complexity issues

My solution scored 100% correctness, but 0% Performance. I just can't figure out how to minimize complexity time.

Problem:

Write a function:

int solution(int A[], int N);


that, given an array of N positive integers, returns the maximum number of trailing zeros of the number obtained by multiplying three different elements from the array. Numbers are considered different if they are at different positions in the array.

For example, given A = [7, 15, 6, 20, 5, 10], the function should return 3 (you can obtain three trailing zeros by taking the product of numbers 15, 20 and 10 or 20, 5 and 10).

For another example, given A = [25, 10, 25, 10, 32], the function should return 4 (you can obtain four trailing zeros by taking the product of numbers 25, 25 and 32).

Assume that:

• N is an integer within the range [3..100,000];
• each element of array A is an integer within the range [1..1,000,000,000].

Complexity:

• expected worst-case time complexity is $O(N*log(max(A)))$;
• expected worst-case space complexity is $O(N)$ (not counting the storage required for input arguments).

Solution:

the idea:

1. factorize each element into pairs of 5's and 2's
2. sum each 3 pairs into one pair - this costs $O(N³)$
3. find the pair who's minimum coordinate value is the biggest
4. return that minimun coordinate value

the code:

int solution(int A[], int N) {
int fives = 0, twos = 0, max_zeros = 0;
int(*factors)[2] = calloc(N, sizeof(int[2])); //each item (x,y) represents the amount of 5's and 2's of the corresponding item in A

for (int i = 0; i< N; i++) {
factorize(A[i], &fives, &twos);
factors[i][0] = fives;
factors[i][1] = twos;
}

//O(N^3)
for (int i = 0; i<N; i++) {
for (int j = i + 1; j<N; j++) {
for (int k = j + 1; k<N; k++) {
int x = factors[i][0] + factors[j][0] + factors[k][0];
int y = factors[i][1] + factors[j][1] + factors[k][1];
max_zeros = max(max_zeros, min(x, y));
}
}
}
return max_zeros;
}

void factorize(int val, int* fives, int* twos) {
int tmp = val;
*fives = 0, *twos = 0;

if (val == 0) return;
while (val % 5 == 0) { //factors of 5
val /= 5;
(*fives)++;
}
while (val % 2 == 0) { //factors of 2
val /= 2;
(*twos)++;
}
}


I can't figure out how else i can iterate over the N-sized array in order to find the optimal 3 items in time $O(N*log(max(A)))$.

• i dont know how to get to O(N * log(max(A))) but you get to O(N*log(N)) with sorting the array and doing binary search (dont know if the binary search is requeried). and when you have sorted it you can probalby throw away a big portion of the arr. – baot Jun 21 '18 at 14:01

You don't need to perform a full search. Instead, we can transform it into a simple 2D geometry problem. Consider the values as vectors in the "two" and "five" directions (which is equivalent to what you've already done). For the example [25, 10, 25, 10, 32], we have two vectors 0,2, two of 1,1, and one of 5,0.
Now, you're looking for the sum of vectors that maximises the smaller dimension. We can start by choosing the value with the largest minimum dimension (that's one of the 1,1 vectors). From there, choose the next value that maximises the minimum dimension (the other 1,1). From there, neither of the alternatives increases the minimum dimension, so our first partial result is 2.
Next, backtrack and choose the next-best value (5,0). Now, the best value to add to this (to exceed the current best) is one with a large "five" dimension, namely (0,2).