Smallest Number With At least N Trailing Zeros In Factorial

Easy
0/40
Average time to solve is 10m
profile
Contributed by
16 upvotes
Asked in companies
OYOSalesforce

Problem statement

You are given a positive integer N. Your task is to find the smallest number whose factorial contains at least N trailing zeroes.

Example : 
Let N = 1. The smallest number whose factorial contains at least 1 trailing zeroes is 5 as 5! = 120.
Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The very first line of input contains an integer ‘T’ denoting the number of test cases. 

The first line and only line of every test case contain an integer ‘N’ denoting the number of trailing zeros.
Output format : 
For each test case, the smallest number whose factorial contains at least N trailing zeroes is printed.

Output for each test case is printed on a separate line.
Note : 
You do not need to print anything, it has already been taken care of. Just return the answer.
Constraints : 
1 <= T <= 10
0 <= N <= 10^8

Time Limit: 1 sec
Sample Input 1 :
2
1
2
Sample Output 1 :
5
10
Explanation For Sample Input 1 :
For the first test case, refer to the example explained above.

For the second test case, we have, N = 2.
The smallest number whose factorial contains at least 2 trailing zeros is 10 as 10! = 36,28,800.
Sample Input 2 :
2
3
0
Sample Output 2 :
15
0
Hint

Can you solve this problem by generating all the factorials?

Approaches (2)
Generating All Factorials
  • A brute force approach could be to generate factorials of numbers starting from 0.
  • For every factorial, we find the number of trailing zeros. This can be done as follows:
    • Let fact store the factorial of the current number and count store the number of trailing zeros in fact. Initially, we set count to 0.
    • Now, repeat the following steps until fact > 0 and fact%10 = 0 (i.e. last digit of fact is zero):
      • Increment the count by one.
      • Discard the last digit in fact, i.e. fact = fact / 10
    • count stores the number of trailing zeros.
  • If for a number, its factorial has at least N trailing zeros, then this number will be our answer.

 

Note:

 

  • This approach may only work for very small values of N. For larger values of N, calculating factorial may result in an integer overflow.
Time Complexity

O(M), where M is the smallest number whose factorial contains at least N trailing zeroes.

 

We are calculating all the factorials from 0 to M which requires O(M) time. For each factorial, we are counting the number of trailing zeros which requires constant time. Hence, the overall time complexity is O(M). Note that M! can be very large for large values of N.

Space Complexity

O(1)

 

Only constant extra space is required.

Code Solution
(100% EXP penalty)
Smallest Number With At least N Trailing Zeros In Factorial
Full screen
Console