Find the number of trailing zeroes in the factorial of a given number.

Problem : Find the number of trailing zeroes in the factorial of a given number.

This is an interesting problem. Simple way to solve this is to find the factorial of the number and then count the number of trailing zeroes. But there is a more efficient way to find the number of trailing zeroes, without even finding the factorial of the number. The number of trailing zeroes in 5! is 1, 10! is 2, 15! is 3, 20! is 4, but 25! is 6. Then 30! is 7, 35! is 8, 40! is 9, 45! is 10 but 50! is 12 and so on. So for every multiple of 25, the number of zeroes increases by 2 and for every multiple of 5, the number of zeroes increase by 1. So any number less than 5 has 0 trailing zeroes. Any number between 5 and 10 will have 1 zero, between 10 and 15 will have 2 zeroes and so on. Here is a simple C program implementation of this algorithm.

import java.io.BufferedReader;
import java.io.InputStreamReader;

/**
 * 
 * @author blogkoder
 *
 */
public class TrailingZeroesCalculator
{
    public static void main(String[] args) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        System.out.print("Enter an integer - ");
        
        int number = Integer.parseInt(br.readLine());
      
        System.out.println("The number of trailing zeroes in " + number + " factorial is " + findTrailingZeroes(number));
    }
    
    public static int findTrailingZeroes(int number)
    {
       int trailingZeroes = 0;
       int loopCounter = 0;
     
       number -= 5;
     
       while (number >= 0)
       {
           trailingZeroes++;
           loopCounter++;
         
           if (loopCounter == 5)
           {
               trailingZeroes++;
               loopCounter = 0;
           }
         
           number -= 5;
       }
     
       return trailingZeroes;
    }
}