Smallest factorial number binary search

QUESTION

Given a number n. The task is to find the smallest number whose factorial contains at least n trailing zeroes.\n\nExamples:\n\nInput : n = 1\nOutput : 5 \n1!, 2!, 3!, 4! does not contain trailing zero.\n5! = 120, which contains one trailing zero.\n\nInput : n = 6\nOutput : 25\n25! = 15511210043330985984000000\n\nInput:\nThe first line of input contains an integer T denoting the no of test cases. Then T test cases follow. Each test case contains an integer n.\n\nOutput:\nFor each test case in a new line print the required output.\n\nConstraints:\n1<=T<=100\n1<=n<=100\n.

ANSWER

// C++ program tofind smallest number whose
// factorial contains at least n trailing
// zeroes.
#include<bits/stdc++.h>
using namespace std;
 
// Return true if number's factorial contains
// at least n trailing zero else false.
bool check(int p, int n)
{
    int temp = p, count = 0, f = 5;
    while (f <= temp)
    {
        count += temp/f;
        f = f*5;
    }
    return (count >= n);
}
 
// Return smallest number whose factorial
// contains at least n trailing zeroes
int findNum(int n)
{
    // If n equal to 1, return 5.
    // since 5! = 120.
    if (n==1)
        return 5;
 
    // Initalising low and high for binary
    // search.
    int low = 0;
    int high = 5*n;
 
    // Binary Search.
    while (low <high)
    {
        int mid = (low + high) >> 1;
 
        // Checking if mid's factorial contains
        // n trailing zeroes.
        if (check(mid, n))
            high = mid;
        else
            low = mid+1;
    }
 
    return low;
}
 
// driver code
int main()
{
    int t, n, i ;
  cin>>t;
  
  for(i=1;i<=t;i++)
  {   cin>>n;
    cout << findNum(n) << " ";
  }
    return 0;
  
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.