Searching: Given an number, find the numbers whose factorials end with n zeros

Problem Statement:

You are given a number “n”.

You need to find the number of +ve integers whose factorial ends with n zeros.

Example:

Input: n = 2

Output: 10, 11, 12, 13, 14

10! = 3,628,800
11! = 39,916,800
12! = 479,001,600
13! = 6,227,020,800
14! = 87,178,291,200

Solution 1: Bruteforce approach

Iterate through the range of arrays and then print the numbers who has trailing zeros.

Solution 2: Binary Search

In this approach, we will use binary search to find the first number with n trailing zeros.

From there find all numbers with n trailing zeros.

Time Complexity: O(log(m))
Space Complexity: O(n) // n is number of trailing zeros

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int countTrailingZeroes(int n)
{
    int cnt = 0;
    while (n > 0) 
    {
        n /= 5;
        cnt += n;
    }
    return cnt;
}

void solution(int n)
{
    int low = 0;
    int high = 1e6;

    while (low < high) 
    {
        int mid = (low + high) / 2;
        int count = countTrailingZeroes(mid);
        if (count < n)
            low = mid + 1;
        else
            high = mid;
    }

    vector<int> result;
    while (countTrailingZeroes(low) == n) 
    {
        result.push_back(low);
        low++;
    }

    for (int i = 0; i < result.size(); i++) 
        cout << result[i] << " ";
}

int main()
{
    int n = 2;
    solution(n);
    return 0;
}

Output

10 11 12 13 14