trjhtr

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)))$.

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).

This reasoning should now lead you to a way to order the array (or multiple copies of the array) so that we can short-circuit as many branches of this backtracking as possible (i.e. be able to say "with this position, we'll never see a value that can improve our score; finish this branch now").