# Factorial Zeros

#### CONCEPTS USED:

Binary Search, Mathematics

Hard

#### PROBLEM STATEMENT`(`SIMPLIFIED`)`:

Given a number `N`, your task is to find the count of all such numbers that have `N` trailing zeros in their factorial.

See original problem statement here

#### For Example:

``````Input : N = 2

Output : 5

Explanation :

All these 5 numbers have 2 trailing zeros.

10! = 3628800

11! = 39916800

12! = 479001600

13! = 6227020800

14! = 87178291200``````

OBSERVATION:

1. The solution of this problem will be either `0` or `5`.

2. `0` if no such number is found whose factorial has `N` trailing zeros.

3. `5` because if a number has `N` trailing zeros then its 4 neigbouring numbers will also have the same trailing zeros.

For Example:
`(10, 11, 12 , 13, 14)` all will have 2 trailing zeros in their factorial. Similarly
`(15, 16, 17, 18, 19)` all will have 3 trailing zeros in their factorial.
Similary all such group of 5 numbers contain the same number of trailing zeros in their factorial.

Important Point:
We just need to find a single number that has `N` trailing zeros and our answer will be `5` else `0`.

Can we use `Binary Search` here ?

We need to find a single number between `0` and `5*N` that has `N` trailing zeros. We can go through online coding classes and use `Binary Search` for efficiently searching it in `Logarithmic Time Complexity`.

Why `5*N`?

`5*N` is the upper bound and any number whose factorial has `N` trailing zeros will be less than the factorial of `5*N`.

#### SOLVING APPROACH:

1. The idea is to use `Binary Search`.

2. Initialize `low` and `high` as `0` and `N*5`.

3. Calculate `mid = low + (high - low)/2` and let us assume that mid is our required number with `N` trailing zeros.

4. Find `trailing-zeros-of-mid` and compare it with `N`, if both are equal return mid.

5. Else if `trailing-zeros-of-mid` > `N`, this implies that our required number lies in the lower half so we update `high = mid - 1`.

6. Else `(``trailing-zeros-of-mid` < `N)` implies that our required number lies in the higher half so we update `low = mid + 1`. And keep on searching for a feasible number till `(low <= high)`, if post this condition number is not found return `0`.

#### ALGORITHM:

``````i = 0
j = 5 * N
mid = (i + j) / 2

while i <= j

If trail_zeros_of_mid = N
print 5

else if trail_zeros_of_mid < N
i = mid + 1

else
j = mid - 1

if i > j
print 0``````

#### SOLUTIONS:

```
#include <stdio.h>
#define ll long long

/* funtion for finding trailing zeroes in a number */
ll TrailingZeroUtil(ll n){
ll sum = 0;
ll five = 5;
while(n >= five){
sum += n/five;
five *= 5;
}
return sum;
}

/* function for searching that number whose
number of trailing zeros is equal to n */
ll TrailingZeros(ll n, ll low, ll high){
while(low <= high){
ll mid = low + (high - low)/2;

//finding trailing zeros of mid
ll trailing_zeros = TrailingZeroUtil(mid);

//checking if mid is our required number
if(trailing_zeros == n)
return mid;

/* if mid has greater trailing zeros than required
we go on searching in the lower half */
else if(trailing_zeros > n)
high = mid - 1;

/* if mid has lesser trailing zeros than required
we go on searching in the righter half */
else
low = mid + 1;
}
//if no number has trailing zeros equal to n return 0
return 0;
}

int main()
{
int t; scanf("%lld", &t);
while(t--){
ll n; scanf("%lld", &n);
ll low = 0;
ll high = n*5;

//find the required number with trailing zeros equal to n
ll ans = TrailingZeros(n, low, high);

//if no number found with n trailing zeros print 0
if(ans == 0)
printf("0\n");

/* if a number is found with n trailing zeros then
even 4 numbers ahead of the number will have the
same number of trailing zeros therefore print 5 */
else
printf("5\n");
}
return 0;
}
```
```
#include <bits/stdc++.h>
using namespace std;
#define ll long long

/* funtion for finding trailing zeroes in a number */
ll TrailingZeroUtil(ll n){
ll sum = 0;
ll five = 5;
while(n >= five){
sum += n/five;
five *= 5;
}
return sum;
}

/* function for searching that number whose
number of trailing zeros is equal to n */
ll TrailingZeros(ll n, ll low, ll high){
while(low <= high){
ll mid = low + (high - low)/2;

//finding trailing zeros of mid
ll trailing_zeros = TrailingZeroUtil(mid);

//checking if mid is our required number
if(trailing_zeros == n)
return mid;

/* if mid has greater trailing zeros than required
we go on searching in the lower half */
else if(trailing_zeros > n)
high = mid - 1;

/* if mid has lesser trailing zeros than required
we go on searching in the righter half */
else
low = mid + 1;
}
//if no number has trailing zeros equal to n return 0
return 0;
}

int main()
{
int t; cin>>t;
while(t--){
ll n; cin>>n;
ll low = 0;
ll high = n*5;

//find the required number with trailing zeros equal to n
ll ans = TrailingZeros(n, low, high);

//if no number found with n trailing zeros print 0
if(ans == 0)
cout<<0<<"\n";

/* if a number is found with n trailing zeros then
even 4 numbers ahead of the number will have the
same number of trailing zeros therefore print 5 */
else
cout<<5<<"\n";
}
return 0;
}
```
```
import java.util.*;
import java.io.*;

public class Main {
static long TrailingZeroUtil(long n){
long sum = 0;
long five = 5;
while(n >= five){
sum += n/five;
five *= 5;
}
return sum;
}

/* function for searching that number whose
number of trailing zeros is equal to n */
static long TrailingZeros(long n, long low, long high){
while(low <= high){
long mid = low + (high - low)/2;

//finding trailing zeros of mid
long trailing_zeros = TrailingZeroUtil(mid);

//checking if mid is our required number
if(trailing_zeros == n)
return mid;

/* if mid has greater trailing zeros than required
we go on searching in the lower half */
else if(trailing_zeros > n)
high = mid - 1;

/* if mid has lesser trailing zeros than required
we go on searching in the righter half */
else
low = mid + 1;
}
//if no number has trailing zeros equal to n return 0
return 0;
}
public static void main(String args[]) throws IOException {

Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t != 0){
long n = sc.nextInt();
long low = 0;
long high = n*5;

//find the required number with trailing zeros equal to n
long ans = TrailingZeros(n, low, high);

//if no number found with n trailing zeros print 0
if(ans == 0)
System.out.println("0");

/* if a number is found with n trailing zeros then
even 4 numbers ahead of the number will have the
same number of trailing zeros therefore print 5 */
else
System.out.println("5");
t--;
}
}
}
```

Space Complexity: `O(1)`