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++
Leave a Reply