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 go through online coding classes and 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)

Previous post Get the Sun Light
Next post Generate all Pairs of 0 and 1

Leave a Reply

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