Searching and Sorting: Factorial Trailing Zeroes

Problem Statement:

you are given an integer, you need to return the number of trailing zeros in n!.

Example

Input: n = 5
Output: 1
Because the factorial of 5 is 120 which has one trailing 0.

Solution

We know that, to get a trailing zeros, we need to check what will generate a trailing 0?

It is a number multiplied by 10.

So now we need to find out how many 10’s will appear in the expression of the factorial.

Now 10 = 2 * 5. We need to calculate the number of 5 present.

But for some numbers like “25” = “5 * 5” 5 is repeated.

Now we need to calculate the number of 5.

We can do this by n/5 + n/25 + n/125

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <unordered_map>
#include <vector>
#include <sstream> 

using namespace std;

int trailing_zeroes(int n) 
{ 
  int count = 0;
  for ( long i = 5; n / i; i *= 5)
      count += n / i;
  return count;
}


int main()
{
    int n = 100;
    cout << "Count of trailing 0s in " << 100 << "! is " << trailing_zeroes(n)<<endl;
    return 0;
}

Output:

Count of trailing 0s in 100! is 24