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.

Powered By
CHP Adblock Detector Plugin | Codehelppro