Trailing Zeros in Factorial

Moderate

0/80

Average time to solve is 15m

37 upvotes

Asked in companies

Problem statement

You are given an integer N, you need to find the number of trailing zeroes in N! (N factorial).

Note:

1. Trailing zeros in a number can be defined as the number of continuous suffix zeros starting from the zeroth place of a number.
2. For example, if a number X = 1009000, then the number of trailing zeros = 3 where the zeroth place is 0, the tenth place is 0, the hundredth place is 0.
3. ! means “FACTORIAL”. Factorial of a number is calculated by the product of the integer and all integers below it till 1.
4. Value of 0! is 1.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of the input contains an integer T denoting the number of test cases.

The first and the only line of each test case contains an integer N, denoting the number whose number of trailing zeros from N! is to be found.

Output Format:

The only line of output of each test case should contain an integer, denoting the number of trailing zeroes in N!

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10^4
1 <= N <= 10^9

Time Limit: 1sec

Sample Input 1:

1
5

Sample Output 1:

Explanation for Sample Input 1:

The value of 5! is calculated as 5 * 4 * 3 * 2 * 1 = 120. 120 has 1 trailing zero.

Sample Input 2:

2
3
2147

Sample Output 2:

0
534

Hint 1

Hint 2

Find the factorial of the number.

Approaches (2)

Approach 1

Approach 2

Find the factorial of the number

Calculate the factorial of N.
Initialise FACT = 1 to store factorial of N, iterate 1 <= i <= N and do FACT = FACT * i.
Count the number of trailing zeroes in FACT. Initialise ZEROES = 0.
Repeatedly divide the FACT by 10, if the remainder is 0, increase ZEROES by 1. If the remainder > 0, stop and return ZEROES.

Time Complexity

O(N), where N is the given number.

Since we are iterating over all the N numbers finding factorials for them and then calculating their trailing zeros. Therefore, the complexity here becomes order O(N).

Space Complexity

O(1), as we are using constant extra memory.

(100% EXP penalty)

Trailing Zeros in Factorial

Console