CareerCup

The no. of trailing zeros is equal to the number of 5s that are occur as a factor in a number, present in the sequence n! = n.n-1.n-2.....1.1. Example 50 has two 5s (factors) i.e. observed from factors(50) = 2.5.5 OR factors(10) has one 5 i.e. observed from 10 = 2.5

In order to find the no. of such cases where 5 occurs as a factor, we take n/5. This gives us the no. of occurances of 5 as a factor, but it does not give us the exact number of 5s. For example, it will count that 5 occured (is a factor) in 25, but it will not tell us that 5 occured twice in 25 or thrice in 125.

So, to cover this case, we find n/25, and this tells us the number of cases where 25 occurs. But it will not tell the number of times 25 occurs in a given number.

This can be generalized, and we can say, to find the number of cases where 5 occurs, 25 occurs,...5^i occurs. Sum it up to get the answer.

Let us take an example.

50

50/5 = 10, as it occurs in 5, 10, 15, 20, 25, 30, 35, 40, 45, 50

50/25 = 2, as it occurs in 25 and 50

So, our sum is 10 + 2 = 12 ~ Number of trailing zeros.

We can take 5^i for the case where n < 5^i. In our example, we cannot take 5^3 (125), since 125 > 50. Therefore, our summation(50/5^i) = 12, where i = 1, 2

Hope that helps.

#include<stdio.h>
void main()
{
	int n, no = 0, x = 5, i =1;
	printf("Enter the number\n");
	scanf("%d", &n);
	while(n/x != 0)
	{
		no = no + n/(5*i);
		i = i+5;
		x = x *5;
	}
	printf("The total no. of trailing zeros in the number is %d \n", no);
}

The code works fine

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package trailingzeros;

import java.util.Scanner;

/**
 *
 * @author Sushant
 */
public class Main {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        int n;
        int i = 0, x = 5;
        int trailZero = 0;
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter any factorial number to find trailing zeros.");
        n = sc.nextInt();
        //for(int i = 1 ; i <=n ; i++)
        while(x < n)
        {
            trailZero += n / x;
            x = x*5;
        }
        System.out.println("Trailing zeros = "+trailZero);
    }

}

My Ans: Summation of (n/5^i), where i = 1,...,k such that 5^(k+1) > n

Does anyone has a better solution ?

Soln: Summation(n/5^i), i = 1, 2..k such that 5^(k+1) > n

can u please explain hw it has been derived ?

Welcome !

the best way to find x^k in n! where x is prime is
equal to:
[n/x^1]+[n/x^2]+[n/x^3].....until x^p>n
where [n/x^i] is integer value came after deviding n by x^i;
So for the above problem
say 100!
value=[100/5]+100/25+100/125
=20+4+0
=24
so 5^24 is the max power of 5 which devides 100! or there are 24 trailing zero's in 100!

great explanation
http://www.purplemath.com/modules/factzero.htm

The number of zero on the tail of n! is the number prime factor of 5 of n!

public static int tailZeros(int n) {
		int powOf5 = 0;
		int c = n;		
		while(c > 0) {
			powOf5 += c / 5;
			c /= 5;
		}		
		return powOf5;
	}

// Idea:  find how many numbers divisible by 2 and 5 are from
// 1 to n. Since there're always more numbers divisible by 2 than 5,
// we just need to count how many are divisible by 5
unsigned int GetNumberOfTrailingZeroes(unsigned int n)
{
    unsigned int uZeroesCount = 0;

    for (unsigned int i = n; i > 0; i /= 5)
    {
        uZeroesCount += i/5;
    }

    return uZeroesCount;
}