Count 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.”

Examples:

Example 1:
Input: n = 3
Output: 0
Explanation: 3! = 6, no trailing zero.

Example 2:

Input: n = 5
Output: 1
Explanation: 5! = 120, one trailing zero.

Solution:

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution 1: Brute Force

Approach:

  • Find the factorial of the given number and count the zeros from the back till the digit at the last is not equal to zero.
  • But this approach will not work for the number greater than 12,Because it will cause integer overflow.

Code:

C++ Code

#include<bits/stdc++.h>
 
using namespace std;
int factorial(int num) {
  if (num == 0) {
    return 1;
  }
  return num * factorial(num - 1);
}
int main() {
  int n = 10;
  int fact = factorial(n);
  int cnt = 0;
  while (fact % 10 == 0) {
    cnt++;
    fact /= 10;
  }
  cout <<"The trailing zeros are: "<< cnt << endl;
  return 0;
}

Output: The trailing zeros are: 2

Time Complexity: O(N)

Space Complexity: O(1)

Java Code

class Main {
  public static int factorial(int num) {
    if (num == 0) {
      return 1;
    }
    return num * factorial(num - 1);
  }
  public static void main(String args[]) {
    int n = 12;
    int fact = factorial(n);
    int cnt = 0;
    while (fact % 10 == 0) {
      cnt++;
      fact = fact / 10;
    }
    System.out.println("The trailing zeros are: "+cnt);
  }
}

Output: The trailing zeros are: 2

Time Complexity: O(N)

Space Complexity: O(1)

Solution 2 : Counting the powers of 5

Let’s take an example and understand why we have to consider the factors of 5 only.

Num = 12

12! = 12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 479001600

If we multiply a number with 10 then it will form a trailing zero. 10 can be formed by multiplying 2 and 5. So counting the pair’s of (2,5) will give us the trailing zeros.

We can simply take whichever number (2 and 5) is having the lower power. 

Num = 6

Prime factorization of 6 = 1*2*3*4*5*6 
                         = 1*2*3*2*2*5*3*2 
                         = 2^4 * 3^2 * 5^1

Taking whichever number(2 or 5) 
has a lesser power value.

Ans = 1

But If we look carefully there are more multiples of 2 than multiples of 5. Since we have fewer multiples of 5’s in a given number compared to a number of multiple of 2. 

But is it enough to simply calculate the multiples of 5 ?

Consider the above example num = 28

  • Multiples between 1 and 28 are 5,10,15,20,25.
  • 25 can be written as 5*5 
  • We can form 6 pairs of (2,5).
  • No of trailing zeros will be 6.

Simply Counting the factors of 5 will not solve our problem. But we have to count the powers of 5 divided by num.

Code:

C++ Code

#include <iostream>
using namespace std;
 
int main() {
  int n = 28;
  int cnt = 0;
  for (int i = 5; n / i >= 1; i *= 5) {
    cnt += n / i;
  }
  cout <<"The trailing zeros are: "<<cnt << endl;
  return 0;
}

Output: The trailing zeros are: 6

Time Complexity: O(log5N)

Space Complexity: O(1)

Java Code

class Main {
  public static void main(String args[]) {
    int n = 12;
    int cnt = 0;
    for (int i = 5; n / i >= 1; i *= 5) {
      cnt += n / i;
    }
    System.out.println("The trailing zeros are: "+cnt);
  }
}

Output: The trailing zeros are: 6

Time Complexity: O(log5N)

Space Complexity: O(1)

Special thanks to P.C.Bhuvaneshwari for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article