Trailing zeroes in factorial

Trailing zeroes in factorial 

PROBLEM STATEMENT :

Given T testcases and For each testcase an integer N is given as the input.

For each input, Find the number of trailing zeroes in N!. 

 

Expected Time Complexity: O(logN) (for Finding Number of trailing Zeroes for each testcase)

Expected Auxiliary Space: O(1)

Example 1:
Input: () 
5
Output:
1

Explanation:

5! = 120 so the number of trailing zero is 1.

Example 2:
Input: () 
4
Output:
0

Explanation:

4! = 24 so the number of trailing zero is 0.

HINT :   Trailing 0s in n! = Count of 5s in prime factors of n!

                = floor(n/5) + floor(n/25) + floor(n/125) + ..

---

SOLUTION : 

 
#include <iostream>
using namespace std;
int main() {
  int t;
  cin>>t;
  while(t--)
  {
    int n,noOfZeroes=0;
    cin>>n;
    Trailing 0s in n! = Count of 5s in prime factors of n!
    while(n>0)
    {
      noOfZeroes+=(n/5); 
      n/=5;
    }
    cout<<noOfZeroes<<"\n";
  }
}

Time Complexity: O(logN) (for Finding Number of trailing Zeroes for each testcase)
Auxiliary Space: O(1)

Never Stop Learning !!