# Count Trailing Zeroes

Problem Statement: “Given an integer n, return the number of trailing zeroes in n!.

Note that n! = n * (n – 1) * (n – 2) * … * 3 * 2 * 1.”

Examples:

```Example 1:
Input: n = 3
Output: 0
Explanation: 3! = 6, no trailing zero.

Example 2:

Input: n = 5
Output: 1
Explanation: 5! = 120, one trailing zero.
```

### Solution:

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

### Approach:

• Find the factorial of the given number and count the zeros from the back till the digit at the last is not equal to zero.
• But this approach will not work for the number greater than 12,Because it will cause integer overflow.

Code:

## C++ Code

``````#include<bits/stdc++.h>

using namespace std;
int factorial(int num) {
if (num == 0) {
return 1;
}
return num * factorial(num - 1);
}
int main() {
int n = 10;
int fact = factorial(n);
int cnt = 0;
while (fact % 10 == 0) {
cnt++;
fact /= 10;
}
cout <<"The trailing zeros are: "<< cnt << endl;
return 0;
}
``````

Output: The trailing zeros are: 2

Time Complexity: O(N)

Space Complexity: O(1)

## Java Code

``````class Main {
public static int factorial(int num) {
if (num == 0) {
return 1;
}
return num * factorial(num - 1);
}
public static void main(String args[]) {
int n = 12;
int fact = factorial(n);
int cnt = 0;
while (fact % 10 == 0) {
cnt++;
fact = fact / 10;
}
System.out.println("The trailing zeros are: "+cnt);
}
}
``````

Output: The trailing zeros are: 2

Time Complexity: O(N)

Space Complexity: O(1)

### Solution 2 : Counting the powers of 5

Let’s take an example and understand why we have to consider the factors of 5 only.

```Num = 12

12! = 12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 479001600```

If we multiply a number with 10 then it will form a trailing zero. 10 can be formed by multiplying 2 and 5. So counting the pair’s of (2,5) will give us the trailing zeros.

We can simply take whichever number (2 and 5) is having the lower power.

```Num = 6

Prime factorization of 6 = 1*2*3*4*5*6
= 1*2*3*2*2*5*3*2
= 2^4 * 3^2 * 5^1

Taking whichever number(2 or 5)
has a lesser power value.

Ans = 1```

But If we look carefully there are more multiples of 2 than multiples of 5. Since we have fewer multiples of 5’s in a given number compared to a number of multiple of 2.

### But is it enough to simply calculate the multiples of 5 ?

Consider the above example num = 28

• Multiples between 1 and 28 are 5,10,15,20,25.
• 25 can be written as 5*5
• We can form 6 pairs of (2,5).
• No of trailing zeros will be 6.

Simply Counting the factors of 5 will not solve our problem. But we have to count the powers of 5 divided by num.

Code:

## C++ Code

``````#include <iostream>
using namespace std;

int main() {
int n = 28;
int cnt = 0;
for (int i = 5; n / i >= 1; i *= 5) {
cnt += n / i;
}
cout <<"The trailing zeros are: "<<cnt << endl;
return 0;
}
``````

Output: The trailing zeros are: 6

Time Complexity: O(log5N)

Space Complexity: O(1)

## Java Code

``````class Main {
public static void main(String args[]) {
int n = 12;
int cnt = 0;
for (int i = 5; n / i >= 1; i *= 5) {
cnt += n / i;
}
System.out.println("The trailing zeros are: "+cnt);
}
}
``````

Output: The trailing zeros are: 6

Time Complexity: O(log5N)

Space Complexity: O(1)

Special thanks to P.C.Bhuvaneshwari for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article