CODEWITHSUNDEEP
calgorithmperformancetime-complexity
Atalia.d
Atalia.d

Reputation: 131

Codility: MaxZeroProduct - complexity issues

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

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:

Complexity:

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

Upvotes: 1

Views: 1201

Answers (2)

Alexander Anikin
Alexander Anikin

Reputation: 1098

In real world I don't like such meta-thinking, but still, we are faced some artificial problem with some artificial restrictions...

Since space complexity is O(N), we can't afford dynamic programming based on initial input. We can't even make a map of N*factors. Well, we can afford map of N*2, anyway, but that's mostly all we can.

Since time complexity is O(Nlog(max(A))), we can allow ourselves to factorize items and do some simple one-way reduction. Probably we can sort items with count sort - it's a bit more like Nlog^2(max(A)) for 2-index sorting, but big O will even it out.

If my spider sense is right, we should simply pick something out of this counts array and polish it with 1-run through array. Something like best count for 2, then best for 5, and then we can enumerate the rest of elements finding best overal product. It's just heuristic, but dimentions don't lie!

Just my 2 cents

Upvotes: 0

Paul Hankin
Paul Hankin

Reputation: 58221

Since 2^30 > 1e9 and 5^13 > 1e9, there's a limit of 30 * 13 = 390 different pairs of factors of 2 and 5 in the array, no matter how large the array. This is an upper bound (the actual number is 213).

Discard all but three representatives from the array for each pair, and then your O(N^3) algorithm is probably fast enough.

If it's still not fast enough, you can continue by applying dynamic programming, computing P[i,j], the largest product of factors of 2s and 5s of pairs of elements with index <=i of the form x * 2^y * 5^y+j (where x is divisible by neither 2 nor 5). This table can then be used in a second dynamic programming pass to find the product of three numbers with the most 0's.

Upvotes: 1

Related Questions