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