## 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