Skip to main content

Trailing Zeroes in a Factorial

Problem : Given a number, can you find out how many trailing zeroes are there in the factorial of that number.

This is an interesting problem. One solution to this problem is to find the factorial of the given number and then count the trailing zeroes. Here is the code for this - 

/**
   * This will find the number of trailing zeroes
   * in the factorial of a number.
   *
   * @param n
   * @return int
   */
  public static int trailingZeroesInFactorial(int n)
  {
      BigInteger factorial = factorial(n);

      String string = factorial.toString();

      int trailingZeroCount = 0;

      for (int i = string.length() - 1; i >= 0; i--)
      {
          if (string.charAt(i) == '0')
          {
              trailingZeroCount++;
          }
          else
          {
              break;
          }
      }

      return trailingZeroCount;
  }

There is another solution to this problem where in we do not need to find the factorial of the given number in order to find the number of trailing zeroes. You can find more about this here - 


There is a formula to find the number of trailing zeroes in a factorial - 

*                                      k
* TrailingZeroes = summation [ Math.floor ( N / Math.pow(5, i) ) ]
*                                   i = 1
*

where k must be chosen such that Math.pow(5, k+1) > N

Here is the code -

public static int trailingZeroes(int n)
    {
        int trailingZeroCount = 0;

        int k = 0;

        // Find a value k such that Math.pow(5, k+1) > n
        for (int i = 0; i < n; i++)
        {
            if (Math.pow(5, i+1) > n)
            {
                k = i;
                break;
            }
        }

        for (int i = 1; i <= k; i++)
        {
            trailingZeroCount += Math.floor( (n * 1.0) / Math.pow(5, i));
        }

        return trailingZeroCount;
    }
Labels:

Comments

Post a Comment

Popular posts from this blog

Sum of Subsets - Find how many pairs in the given array sum to a given number

Problem : Given an array of integers intArray[] and another integer sum, find how many pairs of numbers in the given array will sum up to the given sum. This problem is one of the most sought after question in interviews. There may be slight variations of this problem. There are many ways to solve this problem. The most efficient solution considering both time and space complexity is the one discussed below - /** * This will find how many pairs of numbers in the given array sum * up to the given number. * * @param array - array of integers * @param sum - The sum * @return int - number of pairs. */ public static int sumOfSubset(int[] array, int sum) {          // This has a complexity of O ( n lg n )         Arrays.sort(array);         int pairCount = 0;         int leftIndex = 0;         int rightIndex = array.length - 1;          // The portion below has a complextiy of         //  O ( n ) in the worst case.         while (array[rightIndex] >= su...
Post a Comment
Read more

Even Integer Iterator

Problem : Given an iterator of integers, can you give me back another iterator which iterates over the given iterator of integers such that the new iterator gives only even integers. There a couple of different ways to solve this problem. * The first option is to create a new list of integers and add only the even integers from the given iterator and then return an iterator by calling list.iterator(). This has a time complexity of O (n) but also has a space complexity of O (n) in the worst case, which is not desirable. Here is the code for it - public static Iterator<Integer> giveEvenIntegersIterator(Iterator<Integer> iterator) { List<Integer> evenIntegers = new ArrayList<Integer>(); if (iterator != null) { while(iterator.hasNext()) { Integer number = iterator.next(); if (number != null && number % 2 == 0) { evenIntegers.add(number); } } } retu...
Post a Comment
Read more

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 m...
3 comments
Read more