[leetcode] Factorial Trailing Zeroes


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.

The factor of 10 is 2 and 5. Given N!, the factor of 5 is always less than 2. So we can just count the number of factor 5 in the factorial of N.

Be careful of the overflow issue.

class Solution {
public:
    int trailingZeroes(int n) {
        int ans = 0;
        long factor = 5; // BUG overflow
        while(n >= factor){
            ans += n / factor;
            factor = factor * 5;
        }
        return ans;
    }
};

Untitled

Leave a comment

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.