Count trailing zeroes in factorial of a number in C++

In this tutorial, we are going to discuss one of the most important asked interview problems which is called Count trailing zeroes in factorial of a number in C++. Trailing zeroes are those zeroes which occur in the ending of a number.

For example:

• Number = 720 has a total of 1 trailing zero.
• Number = 13,07,67,43,68,000 has a total of 3 trailing zero.

This problem can be solved by remembering the following formula,

Trailing zeroes in n! = Count of 5 in prime factors of n!
= floor(n/5) + floor(n/25) + floor(n/125) + so on….

For example:

For n=6

Factorial of 6 is 720 which has a total number of trailing zero = 1.

For n=15

Factorial of 15 is 13,07,67,43,68,000‬ which has total number of trailing zero = 3.

Let us implement the above-mentioned formula in our code.

Code to Count trailing zeroes in factorial of a number in C++

Cpp source code:

// Code to count trailing zeroes in a factorial
#include<bits/stdc++.h> 
using namespace std; 

int main() 
{ 
  int n;
  cout<<"Enter the number: ";
  cin>>n;
   
  // Initializing count to zero
  if(n<=4)
  {
    cout<< "\nTotal number of trailing 0s in factorial of " <<n 
    << " is 0";
  }
  else
  {
    int count = 0; 

      for (int i=5; n/i>=1; i*=5) 
      {
        count += n/i;
      }
      cout<< "\nTotal number of trailing 0s in factorial of " <<n 
        << " is "<< count; 
  }
  return 0; 
}

Input/Output:

Enter the number: 15

Total number of trailing 0s in factorial of 15 is 3

Explanation:

In our code, we are iterating loop in the power of 5, if the power of 5 becomes greater than the number then the loop is terminated and we get our required answer. In every iteration, we are updating count according to the value of n/i.

You may also learn:

Breadth first search (BFS) and Depth first search (DFS) for a Graph in C++

Radix Sort in C++