Sunday, January 11, 2015

LeetCode 172: Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!.
Note: Your solution should be in logarithmic time complexity.
public class Solution {
    public int trailingZeroes(int n) {
        // http://en.wikipedia.org/wiki/Trailing_zero
        
        // Non-negative number doesn't have factorial.
        // The factorial of 0 is 1.
        if (n <= 0)
            return 0;
        
        // Find k so that pow(5, k+1) > n.
        // Add 0.1 to n in case pow(5, k+1) = n.
        int k = (int)Math.ceil(Math.log(n+0.1)/Math.log(5.0)-1);
        
        if (k < 1)
            return 0;
        
        // The number of trailing zeros
        int ntz = 0;
        
        for (int i = 1; i <= k; i++)
            ntz += n/Math.pow(5, i);
        
        return ntz;
    }
}

No comments:

Post a Comment