HackerRank Number Theory – Manasa and Factorials

Challenge: Manasa and Factorials

Subdomeniu: Number Theory (number-theory)

Scor cont: 40.0 / 40

Submission status: Accepted

Submission score: 1.0

Submission ID: 464738811

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/manasa-and-factorials/problem

Cerinta

Manasa was sulking her way through a boring class when suddenly her teacher singled her out and asked her a question. He gave her a number **n** and Manasa has to come up with the smallest number **m** which contains atleast **n** number of zeros at the end of **m!**. Help Manasa come out of the sticky situation. 

**Input Format**  
The first line contains an integer _T_ i.e. the number of Test cases.  
Next T lines will contain an integer n.  

**Output Format**  
Print smallest such number m. 

**Constraints**  
1 ≤ _T_ ≤ 100 <br>
1 ≤ _n_ ≤ 10<sup>16</sup>  

**Sample Input**  

	3
	1
	2
	3

    
**Sample Output**  

	5
    10
    15


**Explanation**

1. As 4! = 24 and 5! = 120, so minimum value of m will be 5.
2. As 9! = 362880 and 10! = 3628800, so minimum value of m will be 10.
3. As 14! = 87178291200 and 15! = 1307674368000, so minimum value of m will be 15.

Cod sursa

#include <cstdio>

long long no_of_zeroes(long long n)
{
    long long zero_count = 0, five_power = 5;

    while(five_power <= n)
    {
        zero_count += n/five_power;
        five_power *= 5;
    }

    return zero_count;
}

void solve()
{
    long long minimum_zeroes, ans;
    scanf("%lld", &minimum_zeroes);

    long long low = 1, high = 5e16;

    while(low <= high)
    {
        long long mid = (low + high) >> 1;

        if(no_of_zeroes(mid) == minimum_zeroes)
        {
            while(no_of_zeroes(mid) == minimum_zeroes)
                mid--;

            ans = mid + 1;
            break;
        }
        else if(no_of_zeroes(mid) < minimum_zeroes)
        {
            low = mid + 1;
        }
        else if(no_of_zeroes(mid) > minimum_zeroes)
        {
            if(no_of_zeroes(mid - 1) < minimum_zeroes)
            {
                ans = mid;
                break;
            }

            high = mid - 1;
        }
    }

    printf("%lld\n", ans);
}

int main()
{
    int no_of_test_cases;
    scanf("%d", &no_of_test_cases);

    while(no_of_test_cases--)
        solve();

    return 0;
}