Last Updated: 5 Feb, 2021

Smallest Number With At least N Trailing Zeros In Factorial

Easy

Asked in companies

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.

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

Approaches

01 Approach

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.

02 Approach

The brute force approach will not work for larger values of N. So, we need to find a better approach.
If we observe, a trailing zero is produced by the multiplication of prime factors 2 and 5. Hence, we need at least one occurrence of 2 and 5 in the prime factorization of factorial to get a trailing zero.
We can use this observation to find the pattern. Let’s see a few examples:
- 0! (= 1) has no trailing zeros. Also, all the numbers from 0 to 4 have no trailing zeros, due to the absence of prime factors 2 and 5.
- 5! (= 120) has one trailing zero. All the numbers from 5 to 9 have 1 trailing zero, due to the presence of prime factors 2 and 5, where 5 occurs only once.
- Similarly, the factorial of numbers 10 to 14 have 2 trailing zeros.
- Factorial of numbers 20 to 24 have 4 trailing zeros.
- Factorial of numbers 25 to 29 have 6 trailing zeros (one extra because 25 has two fives in its prime factorization), and so on.
From this, we can observe that the minimum value containing at least N trailing zeros is always less than or equal to 5*N.
So we can apply a binary search in the range 0 to 5*N to find the smallest number.
For every iteration in binary search, we need to check if the current number has at least N trailing zeros in its factorial. This can be found using the formula:
- Trailing 0s in X! = Number of 5s in the prime factorization of X!
- i.e Trailing 0s in X! = floor(X / 5) + floor(X / 25) + floor(X / 125) + .......
- The above formula is derived using the observation that in the prime factorization of a factorial, the number of 5s is always less than the number of 2s. Hence, the number of trailing zeros only depends on the number of 5s. (For more information you can refer to a previously solved problem "Trailing Zeros in Factorial").

Algorithm:

Initialize two variables low and high to 0 and 5*N respectively. These are used in our binary search.
Repeat the following steps until low < high:
- Find the middle value, i.e. mid = (low + high)/2.
- Check if the factorial of mid contains at least N trailing zeros. This can be done using the formula mentioned above. Let the number of trailing zeros in mid! be count.
- If count >= N: Set high = mid. This means that mid can be our answer but we need to check if there is any other number smaller than mid and with count >= N.
- Otherwise, set low = mid + 1. As, count < N, hence, mid cannot be our answer. So, we check for numbers greater than mid in hope of finding a number with count >= N.
Return low.

Similar problems

First Digit One

Posted: 14 Oct, 2025

Special Digit Numbers

Posted: 31 Oct, 2025

Minimize Maximum Adjacent Distance

Posted: 3 Nov, 2025

Sorted Doubly Linked List to Balanced BST

Posted: 3 Nov, 2025

Minimized Maximum of Products Distributed to Any Store

Posted: 22 Feb, 2026