**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 = 3Output:0Explanation:3! = 6, no trailing zero.Example 2:Input:n = 5Output:1Explanation:5! = 120, one trailing zero.

**Solution:**

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

**Solution 1: Brute Force**

**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^1Taking 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 toplease check out this articleP.C.Bhuvaneshwarifor contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam,