Given an integer

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

**Understand the problem:**

The naive solution would be first calculate the n!, can then count how many number of zeros. Here the question requires the log time complexity.

Let's take several examples then we may find some patterns.

5 ! = 1 * 2 * 3 * 4 * 5 = 120, -> 1 zero

6 ! = 1 * 2 * 3 * ... * 6 = 720, -> 1 zero

10 ! = 1 * 2 * ... * 5 * ... 10 = 362800 -> 2 zeros.

Therefore, the number of trailing zeros are determined by the number of pair of (2 ,5) for the number. Since number of 2 are always greater than number of 5. We only need to count how many 5s in the number.

**Code (Java):**

public class Solution { public int trailingZeroes(int n) { if (n <= 0) { return 0; } int count = 0; while (n > 1) { count += n / 5; n /= 5; } return count; } }

**Update on 10/14/15:**

public class Solution { public int trailingZeroes(int n) { if (n < 5) { return 0; } int count = 0; for (long i = 5; n / i > 0; i *= 5) { count += n / i; } return count; } }

## No comments:

## Post a Comment