My Very Simple Java Solution with Clear Explanation


  • 0
    W

    With the observation that trailing zeroes are originated from 2x5s. We only need to count number of 5 factors in the product 123*...*n.
    The number of 5 factors of 1x...x5 is 1
    The number of 5 factors of 1x...x25 is 1 x 5 + 1= 6 (because 25 has one more 5 than 5)
    The number of 5 factors of 1x...x125 is 6 x 5 + 1 = 31 (because 125 has one ore factor than 25)
    .....
    So we can calculate the number of 5 factors of 5i
    We can convert number n in to base 5. (d1d2...dk)5. The result just = dk * 1 + dk-1 * 6 + dk-2 * 31 + ....

    Below is the code implementation. The time complexity is O(logn) and space complexity is O(1).

    public int trailingZeroes(int n) {
        /*5, 25, 125, trailing zeroes number conforms the relation f(25) = f(5) * 5 + 1
        f(125) = f(25) * 5 + 1, .... etc
        then convert number n in base 5. The result is the summation of all digit times the corresponding count of that digit.
        */
        
        int res = 0;
        int count = 0;
        while(n > 0) {
            res += (n % 5) * count;
            count = count * 5 + 1;
            n = n / 5;
        }
        return res;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.