Tuesday, December 30, 2014

LeetCode 172 Factorial Trailing Zeroes

Problem

Given an integer n, return the number of trailing zeroes in n!. Note: Your solution should be in logarithmic time complexity.

This is a newly added problem in LeetCode, just yesterday. As a Chinese, I firstly searched what is "Trailing Zeros". OK, it's just the zeros at the end of a decimal number.
Before a depth thinking, I have known that the number of trailing zeros have a close relationship with the number of "5". So I wrote a small python script to try factorials below 10!. Here is the result:
1  1
2  2
3  6
4  24
5  120
6  720
7  5040
8  40320
9  362880
10 3628800

Looks like the number of trailing zeros is associated with the number of numbers could be divided by 5, so I wrote answer:
int trailingZeroes(int n) { return n / 5; }
While, it's still hard to me to get the right answer just one submit. When the input is 30, the right answer is 7 but my answer is 6. OK, I printed out all the factorials less than 28, something aren't went well after 25:
24 620448401733239439360000
25 15511210043330985984000000
26 403291461126605635584000000

After multiplied by 25, there increased 2 zeros. 25 is the square of 5, so it multiplied two 5 to 24!, so it added 2 zeros. Same thing, 125 means there are three 5 multiplied to last number, added 3 zeros. Looks like for factorial, the result is,
return n / 5 + n / 25 + n / 125 + n / 625 + n / 3125;

This could pass the test in LeetCode, but if n is too large, this is not a universal result. The best is
int trailingZeroes(int n) {
    int c = 0;
    while (n >= 5) {
        n /= 5;
        c += n;
    }
    return c;
}


By the way, StackEdit is a great!!!
Written with StackEdit.

No comments:

Post a Comment