Count trailing zeros in factorial of a number.

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! = 120
Number of Trailing Zero = 1

Example: 7! = 5040
Number of Trailing Zero = 1

Example: 10! = 3628800
Number of Trailing Zero = 2

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

Count trailing zeros in factorial of a number

Algorithm

---

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

Trailing 0 will come into number when any number is multiplied by 10.

10 * 1   = 10      (when 10 appears once in multiplication, then trailing zero is 1)
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.
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.

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.

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.
Example, 25(5*5), 125(5*5*5) etc.

This means that there are 5 multiples of 5 in the number 29 – which is correct because there’s
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 = 1 trailing zeros.
Now, check how many times special case 125 occurs in 29 = 29/125 = 0 trailing 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,

1. Divide the number by 5, to find out how much 5 factors are present, then,  
2. 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, 
3. 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;
    }
}

Another Way of writing the same program

package javabypatel;

public class CountTrailingZero {
    public static void main(String[] args) {
        int number = 125;

        int count = 0;
        int divider = 5;

        while ((number/divider) > 0) {
            count += number/divider;
            divider = divider * 5;
        }
        System.out.println(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.