Factorial Trailing Zeroes

Question: Given an integer n, return the number of trailing zeroes in n!.

You may view the full question here.

Approach 1: I highly recommend you to take a look at some of the discussions here. The solution below is inspired by these posts.

Let’s try to visualize the problem at hand. Consider we need to find the number of trailing zeroes for 50!.

Every trailing zero is due to a possible factor of 10. 10 can be broken down as 2 x 5. So, if we were to find 5!, it would have been —

1 x 2 x 3 x 4 x 5

The 2 x 5 in the combination above contributes a factor of 10, which in turn contributes a trailing zero. Actually —

1 x 2 x 3 x 4 x 5

there are more 2s than we need. So, if we just kept tab of the 5s, we could possibly compute the trailing zeroes.

Now, let’s consider our original problem of 50! and try to observe the pattern.

Every 5th element contributes a 5 and hence at least one trailing zero each. Similarly, every 25th element contributes two 5s. And so on…

Consider the above example. 50 can be divided into 10 chunks of 5 i.e., 50/5=10. So, we know that we will find at least 10 trailing zeroes. Now, we check further to see if there are any elements that possibly contribute extra 5s. A simple way to do so is to keep dividing till we can no longer have enough to make a unit of 5.

Step 1: 50/5=10

Step 2: (previous result) 10/5=2

[Explanation: Elements 25 and 50 contribute extra 5s]

Step 3: (previous result) 2/5=0

[Now we stop]

We could express this recursively as —

//Approach 1:
//Runtime: 1ms
//Memory usage: 33.2MB
class Solution {
    public int trailingZeroes(int n) {
        if(n==0){
            return 0;
        }
        return n/5 + trailingZeroes(n/5);
    }
}

Approach 2: In the previous approach, we could just skip the checks for n = 0 to 4.

//Approach 2:
//Runtime: 0ms
//Memory usage: 33.4MB
class Solution {
    public int trailingZeroes(int n) {
        return (n<5)?0: (n/5 + trailingZeroes(n/5));
    }
}

Find more posts here.

Cheers & Chao!