Smallest number with at least n trailing zeroes in factorial

Given an integer n, find the smallest positive integer x such that the factorial of x (i.e., x ! ) contains at least n trailing zeroes.

Examples :

Input: n = 6
Output: 25
Explanation: 25! = 15511210043330985984000000, It ends with 6 trailing zeroes, which is the minimum required.
Input: n = 1
Output: 5
Explanation: 5! = 120, It ends with 1 trailing zero, which meets the requirement.

Try it on GfG Practice

Table of Content

[Naive Approach] Simple Loop-Based Search - O( n × log n) Time and O(1) Space
[Expected Approach] Binary Search on Answer

[Naive Approach] Simple Loop-Based Search - O( n × log n) Time and O(1) Space

In this approach, we use a while loop to iterate over each number starting from 1. For each number, we count the number of trailing zeroes in its factorial by continuously dividing it by 5 and adding the result to the answer until the number becomes less than 5. Once the count of trailing zeroes becomes greater than or equal to n, we return the current number as the answer.

C++

#include <iostream>
using namespace std;

int findNum(int n) {
    int num = 1;
    int cnt = 0;
    while (true) {
        int temp = num;

        // count how many times 5 divides 
        // current number
        while (temp % 5 == 0) {
            cnt++;
            temp /= 5;
        }

        // If total trailing zeros counted so far 
        // is at least n, return current number
        if (cnt >= n) {
            return num;
        }

        num++;  
    }
}

int main() {
    int n = 6;
    cout << findNum(n) << endl;
    return 0;
}

Java

public class GfG {
    public static int findNum(int n) {
        int num = 1;
        int cnt = 0;
        while (true) {
            int temp = num;
            // count how many times 5 divides 
            // current number
            while (temp % 5 == 0) {
                cnt++;
                temp /= 5;
            }
            // If total trailing zeros counted so far 
            // is at least n, return current number
            if (cnt >= n) {
                return num;
            }
            num++;
        }
    }

    public static void main(String[] args) {
        int n = 6;
        System.out.println(findNum(n));
    }
}

Python

def findNum(n):
    num = 1
    cnt = 0
    while True:
        temp = num
        # count how many times 5 divides 
        # current number
        while temp % 5 == 0:
            cnt += 1
            temp //= 5
        # If total trailing zeros counted so far 
        # is at least n, return current number
        if cnt >= n:
            return num
        num += 1
        
if __name__ == "__main__":
    n = 6
    print(findNum(n))

using System;

class GfG {
    static int findNum(int n) {
        int num = 1;
        int cnt = 0;
        while (true) {
            int temp = num;
            // count how many times 5 divides 
            // current number
            while (temp % 5 == 0) {
                cnt++;
                temp /= 5;
            }
            // If total trailing zeros counted so far 
            // is at least n, return current number
            if (cnt >= n) {
                return num;
            }
            num++;
        }
    }

    static void Main(string[] args) {
        int n = 6;
        Console.WriteLine(findNum(n));
    }
}

JavaScript

function findNum(n) {
    let num = 1;
    let cnt = 0;
    while (true){
        let temp = num;
        // count how many times 5 divides 
        // current number
        while (temp % 5 === 0) {
            cnt += 1;
            temp /= 5; 
        }
        // If total trailing zeros counted so far 
        // is at least n, return current number
        if (cnt >= n) {
            return num;   
        }
        num += 1;
    }
}

// Driver code
const n = 6;
console.log(findNum(n));

Output

[Expected Approach] Binary Search on Answer

The idea is to use binary search to find the smallest number x such that x! has at least n trailing zeroes. We use Legendre’s formula to count how many times 5 divides numbers from 1 to x, since each 5 contributes to a trailing zero. The count of trailing zeroes increases monotonically, so binary search on the answer space is valid. The first x for which the trailing zero count is ≥ n is the required minimum.

Trailing 0s in x! = Count of 5s in prime factors of x! = floor(x/5) + floor(x/25) + floor(x/125) + ....

In the article for Count trailing zeroes in factorial of a number, we have discussed number of zeroes is equal to number of 5's in prime factors of x!. We have discussed below formula to count number of 5's.

C++

#include <iostream>
using namespace std;

// returns true if factorial of p has at 
// least n trailing zeroes
bool check(int p, int n) {
    int count = 0;
    int factor = 5;

    // count how many times 5 divides numbers 
    // from 1 to p
    while (factor <= p) {
        count += p / factor;
        factor *= 5;
    }

    return (count >= n);
}

// returns the smallest number whose factorial 
// contains at least n trailing zeroes
int findNum(int n) {
    
    // base case: 5! = 120 has 1 trailing zero
    if (n == 1)
        return 5; 
    
     // upper bound is safe since every 5 adds 
     // a trailing zero
    int low = 0;
    int high = 5 * n;

    // binary search to find the minimum number
    while (low < high) {
        int mid = (low + high) / 2;

        // if mid is sufficient, search on 
        // the left side
        if (check(mid, n))
            high = mid;
        else
            low = mid + 1;
    }

    return low;
}

int main() {
    int n = 6;
    cout << findNum(n) << endl;
    return 0;
}