Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!
Searching Interview Programming

Factorial Zeros

Deepanshu

CONCEPTS USED:

Binary Search, Mathematics

DIFFICULTY LEVEL:

Hard

PROBLEM STATEMENT(SIMPLIFIED):

Given a number N, your task is to find the count of all such numbers that have N trailing zeros in their factorial.

See original problem statement here

For Example:

Input : N = 2

Output : 5

Explanation : 

All these 5 numbers have 2 trailing zeros.

10! = 3628800

11! = 39916800

12! = 479001600

13! = 6227020800

14! = 87178291200

OBSERVATION:

  1. The solution of this problem will be either 0 or 5.

  2. 0 if no such number is found whose factorial has N trailing zeros.

  3. 5 because if a number has N trailing zeros then its 4 neigbouring numbers will also have the same trailing zeros.

For Example:
(10, 11, 12 , 13, 14) all will have 2 trailing zeros in their factorial. Similarly
(15, 16, 17, 18, 19) all will have 3 trailing zeros in their factorial.
Similary all such group of 5 numbers contain the same number of trailing zeros in their factorial.

Important Point:
We just need to find a single number that has N trailing zeros and our answer will be 5 else 0.

Can we use Binary Search here ?
We need to find a single number between 0 and 5*N that has N trailing zeros. We can use Binary Search for efficiently searching it in Logarithmic Time Complexity.

Why 5*N?
5*N is the upper bound and any number whose factorial has N trailing zeros will be less than the factorial of 5*N.

SOLVING APPROACH:

  1. The idea is to use Binary Search.

  2. Initialize low and high as 0 and N*5.

  3. Calculate mid = low + (high - low)/2 and let us assume that mid is our required number with N trailing zeros.

  4. Find trailing-zeros-of-mid and compare it with N, if both are equal return mid.

  5. Else if trailing-zeros-of-mid > N, this implies that our required number lies in the lower half so we update high = mid - 1.

  6. Else (trailing-zeros-of-mid < N) implies that our required number lies in the higher half so we update low = mid + 1. And keep on searching for a feasible number till (low <= high), if post this condition number is not found return 0.

ALGORITHM:

i = 0
j = 5 * N
mid = (i + j) / 2 

while i <= j

  If trail_zeros_of_mid = N
    print 5

  else if trail_zeros_of_mid < N
    i = mid + 1

  else
    j = mid - 1

if i > j
  print 0

SOLUTIONS:


#include <stdio.h>
#define ll long long

/* funtion for finding trailing zeroes in a number */
ll TrailingZeroUtil(ll n){
    ll sum = 0;
    ll five = 5;
    while(n >= five){
        sum += n/five;
        five *= 5;
    }
  return sum;
}

/* function for searching that number whose 
  number of trailing zeros is equal to n */
ll TrailingZeros(ll n, ll low, ll high){
  while(low <= high){
    ll mid = low + (high - low)/2;

    //finding trailing zeros of mid 
    ll trailing_zeros = TrailingZeroUtil(mid);

    //checking if mid is our required number
    if(trailing_zeros == n)
      return mid;

    /* if mid has greater trailing zeros than required
        we go on searching in the lower half */
    else if(trailing_zeros > n)
      high = mid - 1; 

    /* if mid has lesser trailing zeros than required
        we go on searching in the righter half */
    else
      low = mid + 1;
  }
  //if no number has trailing zeros equal to n return 0
  return 0;
}

int main()
{
  int t; scanf("%lld", &t);
  while(t--){
    ll n; scanf("%lld", &n);
    ll low = 0; 
    ll high = n*5;

    //find the required number with trailing zeros equal to n
    ll ans = TrailingZeros(n, low, high);

    //if no number found with n trailing zeros print 0
    if(ans == 0)
      printf("0\n");

    /* if a number is found with n trailing zeros then 
    even 4 numbers ahead of the number will have the 
    same number of trailing zeros therefore print 5 */
    else
      printf("5\n");
  }
  return 0;
}


#include <bits/stdc++.h>
using namespace std;
#define ll long long

/* funtion for finding trailing zeroes in a number */
ll TrailingZeroUtil(ll n){
    ll sum = 0;
    ll five = 5;
    while(n >= five){
        sum += n/five;
        five *= 5;
    }
  return sum;
}

/* function for searching that number whose 
  number of trailing zeros is equal to n */
ll TrailingZeros(ll n, ll low, ll high){
  while(low <= high){
    ll mid = low + (high - low)/2;

    //finding trailing zeros of mid 
    ll trailing_zeros = TrailingZeroUtil(mid);

    //checking if mid is our required number
    if(trailing_zeros == n)
      return mid;

    /* if mid has greater trailing zeros than required
        we go on searching in the lower half */
    else if(trailing_zeros > n)
      high = mid - 1; 

    /* if mid has lesser trailing zeros than required
        we go on searching in the righter half */
    else
      low = mid + 1;
  }
  //if no number has trailing zeros equal to n return 0
  return 0;
}

int main()
{
  int t; cin>>t;
  while(t--){
    ll n; cin>>n;
    ll low = 0; 
    ll high = n*5;

    //find the required number with trailing zeros equal to n
    ll ans = TrailingZeros(n, low, high);

    //if no number found with n trailing zeros print 0
    if(ans == 0)
      cout<<0<<"\n";

    /* if a number is found with n trailing zeros then 
    even 4 numbers ahead of the number will have the 
    same number of trailing zeros therefore print 5 */
    else
      cout<<5<<"\n";
  }
  return 0;
}


import java.util.*;
import java.io.*;

public class Main {
  static long TrailingZeroUtil(long n){
      long sum = 0;
      long five = 5;
      while(n >= five){
          sum += n/five;
          five *= 5;
      }
    return sum;
  }

/* function for searching that number whose 
  number of trailing zeros is equal to n */
static long TrailingZeros(long n, long low, long high){
    while(low <= high){
      long mid = low + (high - low)/2;

      //finding trailing zeros of mid 
      long trailing_zeros = TrailingZeroUtil(mid);

      //checking if mid is our required number
      if(trailing_zeros == n)
        return mid;

      /* if mid has greater trailing zeros than required
          we go on searching in the lower half */
      else if(trailing_zeros > n)
        high = mid - 1; 

      /* if mid has lesser trailing zeros than required
          we go on searching in the righter half */
      else
        low = mid + 1;
    }
    //if no number has trailing zeros equal to n return 0
    return 0;
  }
  public static void main(String args[]) throws IOException {

    Scanner sc = new Scanner(System.in);
    int t = sc.nextInt();
    while(t != 0){
      long n = sc.nextInt();
      long low = 0; 
      long high = n*5;

      //find the required number with trailing zeros equal to n
      long ans = TrailingZeros(n, low, high);

      //if no number found with n trailing zeros print 0
      if(ans == 0)
        System.out.println("0");

      /* if a number is found with n trailing zeros then 
      even 4 numbers ahead of the number will have the 
      same number of trailing zeros therefore print 5 */
      else
        System.out.println("5");
      t--;
    }
  }
}

Space Complexity: O(1)

[forminator_quiz id="1106"]
This article tried to discuss Binary Search, Mathematics. Hope this blog helps you understand and solve the problem. To practice more problems on Searching, Mathematics you can check out MYCODE | Competitive Programming.

Leave a Reply

Your email address will not be published. Required fields are marked *

Close

Related Post