DEV Community 👩‍💻👨‍💻

Alkesh Ghorpade
Alkesh Ghorpade

Posted on • Originally published at alkeshghorpade.me

LeetCode - Factorial Trailing Zeroes

Problem statement

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

Note that n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1.

Problem statement taken from: https://leetcode.com/problems/factorial-trailing-zeroes

Example 1:

Input: n = 3
Output: 0
Explanation: 3! = 6, no trailing zero.
Enter fullscreen mode Exit fullscreen mode

Example 2:

Input: n = 5
Output: 1
Explanation: 5! = 120, one trailing zero.
Enter fullscreen mode Exit fullscreen mode

Example 3:

Input: n = 0
Output: 0
Enter fullscreen mode Exit fullscreen mode

Constraints:

- 0 <= n <= 10^4
Enter fullscreen mode Exit fullscreen mode

Explanation

A simple approach is to calculate the factorial of the number first and then count the number of trailing zeroes. The above method can cause overflow for bigger numbers.

The idea is to consider prime factors of a factorial n. A trailing zero is a result of prime factor 2 and 5. We just need to count the number of 2's and 5's.

Consider the example n = 5. There is one 5 and three 2s in prime factors of 5!.

5! = 5 * 4 * 3 * 2 * 1
   = 5 * 2^2 * 3 * 2
   = 2^3 * 3 * 5
Enter fullscreen mode Exit fullscreen mode

And for n = 11, we have two 5s and eight 2s.

11! = 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1
    = 2^8 * 3^4 * 5^2 * 7 * 11
Enter fullscreen mode Exit fullscreen mode

We can easily say that number of 2s is greater than number of 5s. We only need to count the number of 5s in prime factors and we are done.

Count number of 5s in prime factors of n!

The simplest way is to calculate floor(n/5). For example 7! has one 5, 10! has two 5s. But for the case where n is 25, 125, etc we have more than one 5. When we consider 29! we get one extra 5 and the numbers of trailing zeroes becomes 6. To handle this case, we first divide n by 5 and remove all single 5s, then divide by 25 to remove extra 5s and so on.

Trailing 0s in n! = floor(n/5) + floor(n/25) + floor(n/125) + ....
Enter fullscreen mode Exit fullscreen mode

C++ solution

class Solution {
public:
    int trailingZeroes(int n) {
        int count = 0;

        for(long int i = 5; n / i >= 1; i *= 5){
            count += n/i;
        }

        return count;
    }
};
Enter fullscreen mode Exit fullscreen mode

Golang solution

func trailingZeroes(n int) int {
    count := 0

    for i := 5; n / i >= 1; i *= 5 {
        count += n/i
    }

    return count
}
Enter fullscreen mode Exit fullscreen mode

Javascript solution

var trailingZeroes = function(n) {
    let count = 0;

    for( let i = 5; n / i >= 1; i *= 5 ) {
        count += Math.floor(n / i);
    }

    return count;
};
Enter fullscreen mode Exit fullscreen mode

Let's dry-run our algorithm to see how the solution works.

Input: n = 29

Step 1: count = 0

Step 2: loop for i = 5; n / i >= 1
        28 / 5 >= 1
        5 >= 1
        true

        count = count + n / i
              = 0 + 29 / 5
              = 0 + 5
              = 5

        i *= 5
        i = 5 * 5
          = 25

Step 3: n / i >= 1
        28 / 25 >= 1
        1 >= 1
        true

        count = count + n / i
              = 5 + 29 / 25
              = 5 + 1
              = 6

        i *= 5
           = 25 * 5
           = 125

Step 4: n / i >= 1
        28 / 125 >= 1
        0 >= 1
        false

Step 5: return count

So we return the answer as 6.
Enter fullscreen mode Exit fullscreen mode

Top comments (0)

Make Your Github Profile Stand Out

Github is great, but have you considered how to make yours more attractive for potential employers or other visitors? Even non-tech ones like recruiters!

Take a couple of hours and show your best side as a person - and a programmer.