6
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – baot Jun 21 '18 at 14:01
3
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Suppose you're doing this with just one dimension (to make the reasoning simpler). Sort your one-dimensional vectors in decreasing order (e.g. 7, 6, 3, 3, 2, 0). Now, suppose you have already picked 7 and 6 - once you have chosen 3 as your next element, you know that there's nothing higher than 3 still to be chosen. Your challenge is to design a data structure that supports the 2-dimensional case. I'm not going to work through this myself, but I'm guessing you want some kind of sparse matrix, where the entries are counts of how many inputs land in each cell. \$\endgroup\$ – Toby Speight Jun 22 '18 at 9:29
  • \$\begingroup\$ I accidently deleted my earlier response. I'll give it a try and update. thank you! \$\endgroup\$ – Atalia.d Jun 22 '18 at 12:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.