Compute the Number of Trailing Zeros for a Factorial in C++

Given an integer n, return the number of trailing zeroes in Factorial N!

Your solution should be in logarithmic time complexity.

Naive/Bruteforce Solution

It is easy to get the fact that the trailing zeros totally depend on the 5 times 2 only. In other words, we just need to figure out how many 5’s are there in the numbers between 1 to N, and that is the answer because the factor 2 is a lot more than factor 5.

The following solution runs at complexity O(n log n) so it is way slower if the input number is large.

class Solution {
public:
    int trailingZeroes(int n) {
        int r = 0;
        for (int i = 5; i <= n; i ++) {
            int x = i;
            while (x) { // get the number of factor 5 for each number
                if (x % 5 == 0) {
                    r ++;
                    x /= 5;
                } else {
                    break;
                }
            }
        }
        return r;
    }
};

This gives Time Limit Exceed. For example, Last executed input: 1808548329, then this takes like forever to compute.

O(log n)

25 = 5 * 5, there is an additional 5, so is 50, 75 and so on, so take 100 for example, the number of factor 5 is:

100 / 5 + 100 / 25 = 24

The 100/5 refers to 1 single 5 that is: 5, 10, 15, 20 … 100
The 100/25 refers to additional 5 that is: 25, 50, 75, 100

So you get the pattern:

class Solution {
public:
    int trailingZeroes(int n) {
        int r = 0;
        while (n >= 5) {
            r += n / 5;
            n /= 5;
        }
        return r;
    }
};

See also the Python solutions to compute the number of trailing zeros for a Factorial number: Teaching Kids Programming – Compute the Number of Trailing Zeros for Factorial N

–EOF (The Ultimate Computing & Technology Blog) —