Thursday, August 27, 2015

Leetcode: Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!.
Note: Your solution should be in logarithmic time complexity.
Credits:
Special thanks to @ts for adding this problem and creating all test cases.
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