### Count trailing zeros in factorial of a number.

Count trailing zeros in factorial of a number. there are many ways to count trailing 0 in factorial of number. Java program to count trailing zero.

**What is Trailing Zero in a number?**

Trailing zeros are a sequence of 0 in the decimal representation of a number, after which no other digits follow.

**Example:**5! = 12

**0**

**Number of Trailing Zero = 1**

**Example: 7**! = 504

**0**

**Number of Trailing Zero = 1**

**Example:**10! = 36288

**00**

**Number of Trailing Zero = 2**

Below you can get Factorial of number till 20 for testing Trailing Zeros in java program.

### Algorithm

Before looking into the algorithm, let's ask ourselves, when trailing 0 will come into number?

10 * 1 = 10 (when 10 appears once in multiplication, then trailing zero is 1)Trailing 0 will come into number when any number is multiplied by 10.

10 * 2 = 20 (when 10 appears once in multiplication, then trailing zero is 1)

**.**

**.**

**.**

10 * 9 = 90 (when 10 appears once in multiplication, then trailing zero is 1)

10 * 10 = 100 (when 10 appears twice in multiplication, then trailing zero is 2)

It means, number of times 10 appears in a number that much trailing zero will be present.

So, for finding trailing zero in factorial of a number, if we count number of 10's present in a number will give us number of trailing zero in factorial of a number.

Wait... If number doesn't contain 10's factor but contains 2's and 5's factor then also 10 will come into picture as 2*5 = 10.Do we really need to fine 2 and 5 pair, No. If you observe, any number where 5 factor will be present, it is sure 2 will be present as 2 will come before 5.

So, if we find out the number of 2 and 5 pairs present in a factor of number will also give us number of trailing 0s.

**Eg:**5! = 5 * 4 * 3 * 2 * 1

= 5 * (2 * 2) * 3 * 2 * 1

= So number of 2's present in a number will always be more then 5.

In short, if number contains 5, then it must contains 2 as well for any factorial number.

So instead of finding pair of 5 and 2 it is just fine to check 5 present in a number as 2 will obviously present where 5 is present to make up pair.

**Special Case for numbers like 25, 125 .... :**

**How many times 5 is present in a 20! ?**

number=20!, so number of 5's in 20 is 20/5 = 4, so there will be 4 zero in 20!.

**How many times 5 is present in a 29! ?**

number=29!, so number of 5's in 29 is 29/5 = 5.8, so what to do here.

Number of perfect 5 require to make 29! is 5 and 0.8 we can definitely discard. so it is 5 trailing zeros in 29!.

We are wrong here... there are total 6 trailing Zero in 29!, so from where does that extra one Zero came?

So, it is not 5 zeros in 29! but is actually 6 0s (8841761993739701954543616000000).This situation we need to handle for numbers which itself are full multiple of 5.This means that there are 5 multiples of 5 in the number 29 – which is correct because there’s

Example, 25(5*5), 125(5*5*5) etc.

5(5*1), 10(5*2), 15(5*3), 20(5*4), and 25(5*5).

Here, 25 is special because it has 2 factors of 5 (because 5*5 is 25).This means, for number like 25, we should consider that 5 and 2 pair is present twice and not once as like other number.

29! contains 29/5 =5 trailing zeros.

Now, check how many times special case 25 occurs in 29 = 29/25 =1trailing zeros.

Now, check how many times special case 125 occurs in 29 = 29/125 =0trailing zeros.

So 29! factorial contains 5 + 1 + 0 = 6 trailing zeros.

###

Algorithm for Counting trailing zeros in factorial of a number.

So in general, if you want to count trailing zero in factorial of a number, you have to,

- Divide the number by 5, to find out how much 5 factors are present, then,
- Divide the number by 25 to find out how many times 25 are present in a number as it will add extra 5 to number then,
- Divide the number by 125 to find out how many times 125 are present in a number as it will add extra 5 to number and so on.

### Java Program to Count trailing zeros in factorial of a number.

package javabypatel; public class Trailing0sInFactorial { public static void main(String[] args) { int num=5; System.out.println(getTrailing0InFactorial(num)); } public static int getTrailing0InFactorial(int num) { if(num<0) return -1; int count = 0; for (int i = 5; (num/i) > 0; i=i*5) { count = count + num/i; } return count; } }

### You may also like to see

#### Compress a given string in-place and with constant extra space.

#### Check whether a given string is an interleaving of String 1 and String 2.

#### Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord.

#### Serialize and Deserialize a Binary Tree

#### Advanced Multithreading Interview Questions In Java

**Enjoy !!!!**

**If you find any issue in post or face any error while implementing, Please comment.**

## Post a Comment