0
\$\begingroup\$

Test data passes the test, so why does Codility keep failing it? Am I perhaps misunderstanding the requirement?

using System;

class Solution {
    public int solution(int[] A) {
        int max = 0;
        for (var i = 0; i < A.Length; i++) {
            for (var j = i + 1; j < A.Length; j++) {
                for (var k = j + 1; k < A.Length; k++) {
                    var product = A[i] * A[j] * A[k];
                    var zeros = trailingZeros(product);
                    //Console.WriteLine($"{product} - {zeros}");
                    if (zeros > max) {
                        max = zeros;
                    }
                }
            }
        }

        return max;
    }

    private int trailingZeros(int N) {
        if (N == 0) {
            return 0; 
        }
        int count = 0;
        while (!(N <= 0 || N % 10 != 0)) {
            count++;
            N /= 10;
        }
        return count;
    }
}

Test data:

A = [7, 15, 6, 20, 5, 10]
A = [25, 10, 25, 10, 32]
A = [1, 1, 110]
A = [90, 76, 300, 10, 3, 5, 9, 1000000000]
A = [100090, 10030, 1000, 90, 87655, 676345]
A = [85, 65, 20, 50, 1, 0]
A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
A = [10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 3, 90]
A = [101, 307, 890, 208, 406, 701, 222, 445, 5432]
A = [7, 15, 6, 20, 5, 10]
A = [90, 70, 80]
A = [900, 800, 700, 600, 500, 551, 662, 773, 884, 995]

Full description of the problem:

Write a function:

class Solution { public int solution(int[] A); }

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

\$\endgroup\$

closed as off-topic by t3chb0t, Billal Begueradj, Stephen Rauch, Graipher, Malachi Jul 3 '18 at 15:42

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Code not implemented or not working as intended: Code Review is a community where programmers peer-review your working code to address issues such as security, maintainability, performance, and scalability. We require that the code be working correctly, to the best of the author's knowledge, before proceeding with a review." – t3chb0t, Billal Begueradj, Stephen Rauch, Graipher, Malachi
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    \$\begingroup\$ This is equally bad because broken code is off-topic. \$\endgroup\$ – t3chb0t Jul 3 '18 at 15:25
  • 2
    \$\begingroup\$ I have rolled back your last edit. Please see What should I do when someone answers my question?: Do not add an improved version of the code after receiving an answer. Including revised versions of the code makes the question confusing, especially if someone later reviews the newer code. \$\endgroup\$ – t3chb0t Jul 3 '18 at 15:26
  • 1
    \$\begingroup\$ @ostati, please feel free to post the working code and have it reviewed, as a new question. \$\endgroup\$ – Malachi Jul 3 '18 at 15:42
  • 1
    \$\begingroup\$ You will only have trailing zero's if at least 1 number is divisible by 10 OR there is a pair of numbers divisible by 5 and 2. This can reduce the need to multiply triplets over the entire list. \$\endgroup\$ – Rick Davin Jul 3 '18 at 16:59
  • 1
    \$\begingroup\$ Only because someone posts an answer doesn't mean the question isn't off-topic. Do as @Malachi suggested. Fix the code and post a follow-up if you still wish a review. \$\endgroup\$ – t3chb0t Jul 5 '18 at 16:50
2
\$\begingroup\$

You must consider domain boundaries: A can contain integers in the range [1..1,000,000,000] so the largest possible product would be 1,000,000,000^3 which is way beyond int.MaxValue (and even ulong.MaxValue). One way to overcome this problem while keeping you algorithm as is, is to use System.Numerics.BigInteger instead of int.


This conditional expression while (!(n <= 0 || n % 10 != 0)) has its equivalent in while (n > 0 && n % 10 == 0) which I find more straight forward readable.


These nested loops can be optimized a little bit:

    for (var i = 0; i < A.Length; i++) {
        for (var j = i + 1; j < A.Length; j++) {
            for (var k = j + 1; k < A.Length; k++) {
    for (var i = 0; i < A.Length - 2; i++) {
        for (var j = i + 1; j < A.Length - 1; j++) {
            for (var k = j + 1; k < A.Length; k++) {
\$\endgroup\$
2
\$\begingroup\$

I noticed that you have a condition that will never be met inside your trailingZeros private method

private int trailingZeros(int N) {
    if (N == 0) {
        return 0; 
    }
    int count = 0;
    while (!(N <= 0 || N % 10 != 0)) {
        count++;
        N /= 10;
    }
    return count;
}

Particularly:

while (!(N <= 0 || N % 10 != 0))

N <= 0 because N will never be zero or negative

so if you are looking for even a minimal amount of increased performance, you could remove this condition because it will never be met.

When you remove this condition, you are left with

while (!(N % 10 != 0))

which looks funny because it is a negated negative condition. Let's change it to while (N % 10 == 0)

which cleans up the method to this

private int trailingZeros(int N) {
    if (N == 0) {
        return 0; 
    }
    int count = 0;
    while (N % 10 == 0) {
        count++;
        N /= 10;
    }
    return count;
}
\$\endgroup\$

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