Write a program that will calculate the number of trailing zeros in a factorial of a given number

First off, let’s define a factorial for those of you who don’t remember what a factorial of a number is. A factorial of any non-negative integer number “x” is the product of all of the positive integers less than and equal to “x”. This means that the factorial of 4 is 4*3*2*1 which is 24, and the factorial of 6 is 6*5*4*3*2*1 which is 720.

What does the number of trailing zeros mean exactly?




If we want to find the number of trailing zeros this means that we want to calculate how many zeros the factorial of a number ends with – the number of terminating zeros. So, for example, 720 has one trailing zero since it ends with one zero, and 24 has no trailing zeros since it does not end with any zeros at all.

Before we can begin to write a program that will compute the number of trailing zeros of a factorial of a given number, we must come up with an algorithm – basically we need to find a pattern that we can use to write a program. So, let’s start to think about this problem in a way that allows us to find a pattern.




Let’s start by asking ourselves a question. When does a number have a trailing or terminating zero? Well, it should be clear that a number will have a trailing zero if it has a 10 as one of its factors. Remember that a factor of a number “X” is just a number that when multiplied by other numbers gives you “X”. Clearly 720 has a 10 as one of its factors because 10*72 gives us 720. And a number will have 2 trailing zeros if it has 10 as it’s factor 2 times – 10 * 10 * any number will give us a number that ends with 2 zeros. So, it should be clear that the number of 10’s that a number has as it’s factors determines the number of trailing zeros. If there are 2 10’s that are factors, then the number will have 2 trailing zeros. If there are 17 10’s that are factors for a given number, then there will be 17 trailing zeros in that number.

We need to calculate the number of times 10 is a factor to find the trailing zeros

So, the number of factors that are 10’s is equal to the number of trailing zeros. But, wait – 10 has it’s own factors of 5 and 2 – so wouldn’t it be more accurate to say that if a number has factors of 5 and 2 then it also has a 10 as a factor? Yes, that is true. Can we break it down even further? What if we say that the number of times 5 is a factor determines the number of trailing zeros? How accurate is that statement? Well, think about it – if both a 5 and a 2 are factors then that will determine if 10 is a factor, which determines the number of trailing zeros. So, the 5 needs to have a 2 to pair with it to give it a 10. But, almost all factorials have 2 as a factor multiple times – for instance the factorial of 6 is 6*5*4*3*2*1, and 2 is a factor in 2, 4, and 6 – which means that 2 is a factor 3 times, and 5 is a factor once. All we really need is for each 5 to have a 2 to pair with it – but clearly in the factorial of a number the number of 2’s as factors will always exceed the number of 5’s as factors. It’s important that you understand that point, so think it over and/or re-read to make sure it makes sense.

The number of trailing zeros equals the number of times 5 is a factor

So, we can safely assume that any factor of 5 will have a 2 to go with it to give us a 10, which will give us 1 trailing zero. Finally, this means that we just need to count the number of times 5 is a factor in the factorial to get the number of trailing zeros – because we can safely assume that there will always be another 2 as a factor to pair it with. Another key point is that 5 will have to be counted as a factor twice in the number 25 (because 5*5 is 25), three times in the number 125 (because 5*5*5 is 125), and so on. But, 5 is counted as a factor only once in numbers like 10 (5*2), 15 (5*3), 20 (5*4), and so and so forth.

Solution to calculating the number of trailing zeros in factorial




Let’s use some actual numbers to test out our theory. Suppose we have the number 10 as our input – we know that the factorial of 10 is 3628800 – which means that there are 2 trailing zeros. So, applying our pattern – we know that in 10! (which equals 10*9*8*7*6*5*4*3*2*1) there are 2 factors of 5 – one factor is in the number 5 itself and the other factor is in 10 (which is 5*2), and that gives us a total of 2. And, of course, those 2 factors of 5 can be paired with any one of the multiple factors of 2 to give us a 10 twice since 5*2 = 10 (there’s 2, 4, 6, 8, and 10 – remember we said that the numbers of 2’s that are factors will always exceed the number of 5’s that are factors). This means that there should be 2 trailing zeros in the factorial of 10, which there is – so our theory is correct.

What about a bigger number like 29? Why not, instead of counting the number of multiples of 5 that are factors – like 5, 10, 15, etc. – we just divide by 5? If we divide by 5 and round off the number to the lowest integer, we can get the number of multiples of 5 that will be factors in the factorial of a given number. So, if we divide 29 by 5, we get 5.8 – rounding to the lowest integer we get 5. This means that there are 5 multiples of 5 in the number 29 – which is correct because there’s 5, 10, 15, 20, and 25. But wait, remember that 25 is special because it has 2 factors of 5 (because 5*5 is 25). This means that it should count 2 times plus the 4 other factors of 5, which gives us 4+2 = 6. So there are a total of 6 trailing zeros in the factorial of 29, which is correct because 29! is 8841761993739701954543616000000.

An algorithm to find the trailing zeros in factorial

Now that we see the pattern, let’s try to come up with an algorithm that will calculate the number of zeros for a factorial in the context of an actual program:

Suppose we have the input number, let’s call it “n”. If the number “n” is equal to 5, we return a 1. If not, we divide that number by 5 and if we get a number that is a decimal greater than 1, then we should truncate to the lowest integer.


Then we divide “n” by 52 (25), and if we get a number that is a decimal greater than or equal to 1, then we should truncate to the lowest integer, and add 1 to the count of trailing zeros If the number is less than 1 then we stop counting and return.


Then we divide “n” by 53 (125), and if we get a number that is a decimal greater than or equal to 1, then we should truncate to the lowest integer, and add 1 to the count of trailing zeros If the number is less than 1 then we stop counting and return.


And so on…

Here is what a solution looks like in Java pseudocode that implements the algorithm described above to find the number of terminating zeros:

Java solution to find the number of trailing zeros in factorial

public  static  int  findTrailingZeros(int  number)  {

int count = 0;


if(number < 0){

System.out.println("Error: There is no Factorial 
for a number less than 0");

return -1; //error condition

}

if(number == 5){
return 1; 
}


/*
start from 5, multiply j by 5 each loop, but
stop iterating when number/j is no longer greater
than 1
*/
for ( int j = 5; number/j >= 1; j *= 5 )
{
/*
assuming that number/j will just give you the
integer result of the division of number/j and
also truncate:
*/
count  +=  number  /  j;
}

return count;
}

And there we have a solution to the problem – hopefully it was interesting for you!

Hiring? Job Hunting? Post a JOB or your RESUME on our JOB BOARD >>

Subscribe to our newsletter for more free interview questions.

  • AJ

    Anyway I must appreciate the effort you put to write this article. Very helpful. Thank you !

  • AJ

    Under the “An algorithm to find the trailing zeros in factorial” section when you divide by 5^2 or 5^3 and so on and get a value greater than 1…. I find it confusing when you say add ‘1’ to the count. Shouldn’t it be the lower integer value of the division ? Coz that’s what the code does too. I found it a little confusing the way it is put.

  • YouAreAFool

    You are a fool.

  • z0ltan

    Incorrect.

  • Ashutosh Pandey

    System.out.println(“Please enter a number”);

    int n = new Scanner(System.in).nextInt();

    int temp = 10 , count = 0;

    while(true)

    {

    if(n%temp==0)

    {

    count+=1;

    temp*=10;

    }

    else

    {

    System.out.println(“Number of traling zeros “+count);

    break;

    }

    }

  • Guest

    the given algorithm is not correct, when n=1808548329, there should be 452137076 tailing zeros, however it gives 452137080

  • Vikrant Kashyap

    this code will not work when we need to calculate number of trailing zero for more than factorial of 10

  • Bharath Josh

    I thought this would be simpler. But can this be a solution? Enlighten me please.

    public int getZeros(long input) {

    long i = input;

    int zeros = 0;

    if (input > 5) {
    zeros = (int) ((input / 5));
    return zeros;
    }
    return zeros;
    }

  • Debapriyay Mukhopadhyay

    The following article in GanitCharcha provides a nice discussion on the topic.

    http://www.ganitcharcha.com/view-article-A-Note-on-Factorial-and-it's-Trailing-Zeros.html

  • Bernd

    You could also do:

    count = 0;
    */ if… /*
    while(number > 0)
    {
    number /= 5; //assuming its rounded to int
    count += number;
    }
    Your solution might be more readable.

  • cczhang

    this is actually wrong, consider 25 should be counted twice. However it is only counted once in your code

  • tmd25

    or more easy algorithm

    public static int findTrailingZeros(int number) {
    int count = 0;
    for( int i = 1; i<=number; i++)
    {
    if (i%5 == 0)
    {
    count ++;
    }
    }
    return count;
    }

  • dronz3r

    in java code, if(number == 5) block is redundant..

  • Jay

    Awesome.