Trailing Zeros in Factorial
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.

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

Question

Trailing Zeros in Factorial

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.

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

Accepted Answer

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

TC : O(N) , where N is the given number
SC : O(1)

Accepted Answer

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.

Space Complexity: O(1)Explanation:

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

Time Complexity: O(n)Explanation:

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

Accepted Answer

Prime Factors

We know that trailing zero in any number comes if, 10 is a divisor of the number.
10 itself comes from 2*5.
So, we need to keep count of all products of 5 and 2, like 2*5 = 10, 4*5 = 20, etc.
So, if we take all the numbers which are multiples of 5 in the range [1, N]. Then, we have more than enough even numbers available to pair them with multiples of 5.
How many multiples of 5 are there in the numbers from 1 to 100?
- Because 100 ÷ 5 = 20, so, there are twenty multiples of 5 between 1 and 100.
- But wait, actually 25 is 5×5, so each multiple of 25 has an extra factor of 5, e.g. 25 × 4 = 100，which introduces extra one zero.
- So, we need to know how many multiples of 25 are between 1 and 100? Since 100 ÷ 25 = 4, there are four multiples of 25 between 1 and 100.
- Finally, we get 20 + 4 = 24 trailing zeros in 100!. This example tells us, we need to care about 5, 5×5, 5×5×5, 5×5×5×5, etc.
Let’s look at another example, N = 21. Multiples of 5 in the range [1, 21] = 4, namely {5, 10, 15, 20}. So we can pair these numbers with even numbers to generate one extra zero. Now reducing N to N/5, to get additional factors of 5. N = 21/5 = 4. But 4/5 = 0. That means, no more additional zeroes available in 21!, so the number of zeroes in N! is 4.
So, the number of zeros in 21! is 4.

Space Complexity: O(1)Explanation:

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

Time Complexity: O(logn)Explanation:

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

Since we are working to calculate the trailing zeros and only checking it using in terms of powers of two factors 5 and 2 so the complexity here is of order O(log(N)).

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

Note:

Input Format:

Output Format:

Note:

Constraints:

Top Capgemini Senior Software Engineer interview questions & answers

Popular interview questions of Senior Software Engineer

Top HR questions asked in Capgemini Senior Software Engineer