Make delicious recipes!

Find the number of trailing zeroes in factorial(n)



Solution: A trailing zero is formed when a factor of 5 meets a factor of 2.
In a factorial, for ever factor which is a multiple of 5, there is always a factor which is a multiple of 2.
We can rest assured that there will be as many factors of 2 as there are factors of 5.
So if we just count the factors of 5, we will get the count of trailing zeroes.

However, note that 25 adds two trailing zeroes to the output when multiplied by 4.
One of its zeroes we had counted earlier when we were looking for factors of 5 multiplying with factors of 2.
But 25 still had another zero to contribute.
So it must be counted once more.

A similar reasoning holds true for 125 and other powers of 5.
public static void trailingZeroes(int N)
{
    int zeroes = 0;
    for (int i=5; i<200; i=i*5)
    {
        System.out.println("Zeroes from multiples of " + i + " = " + N/i);
        zeroes += N/i;
    }
    return zeroes;
}
Sample Execution for N=200
Zeroes from 5 = 40
Zeroes from 25 = 8
Zeroes from 125 = 1


Note that the line "Zeroes from 5 = 40" above captures single zero contributed by "25, 50, 75 ... 200" also and it also captures single zero contributed by "125". That is why "Zeroes from 25=8" does not attempt to capture two zeroes. It only captures the second zero contributed by "25, 50, 75, 100, 125, 150, 175 and 200" and because it captures second zero contributed by 125 in this process, the next iteration does not attempt to capture the second zero contributed by 125.

Also note that when we divide N by K, the quotient is conventionally understood as the count of K's contained in N
But it also means the count of numbers divisible by K
For example, if N=37 is divided by K=5, we get 7 which means that there are 7 numbers divisible by 5 between 0 and 37
And they are: 5, 10, 15, 20, 25, 30, 35
And each of these multiples of 5 contributes a zero in the factorial

Best part is that we do not have to separately count the zeroes contributed by 10, 20, 30, 100 etc. because
their contribution is already counted in the above method.






Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal