#### CONCEPTS USED:

Binary Search, Mathematics

#### DIFFICULTY LEVEL:

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**:

The solution of this problem will be either

`0`

or`5`

.

`0`

if no such number is found whose factorial has`N`

trailing zeros.

`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:

The idea is to use

`Binary Search`

.Initialize

`low`

and`high`

as`0`

and`N*5`

.Calculate

`mid = low + (high - low)/2`

and let us assume that mid is our required number with`N`

trailing zeros.Find

`trailing-zeros-of-mid`

and compare it with`N`

, if both are equal return mid.Else if

`trailing-zeros-of-mid`

>`N`

, this implies that our required number lies in the lower half so we update`high = mid - 1`

.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)`