Smallest number with at least n trailing zeroes in factorial

Problem Statement

Given a number n, find the smallest number whose factorial has at least n trailing zeroes.

Trailing zeroes in factorial are produced by factors of 10, which come from pairs of 2 and 5. Since factors of 2 are more abundant, we need to count factors of 5.

Constraints:

• 1 ≤ n ≤ 10^9

Example:

• Input: n = 1
• Output: 5
• Explanation: 5! = 120 has 1 trailing zero

Example 2:

• Input: n = 2
• Output: 10
• Explanation: 10! = 3628800 has 2 trailing zeroes

Example 3:

• Input: n = 6
• Output: 25
• Explanation: 25! has 6 trailing zeroes (from 5, 10, 15, 20, 25 contributing 5s, with 25 = 5² contributing an extra)

Background: Counting Trailing Zeroes

Trailing Zeroes Formula

The number of trailing zeroes in n! is given by:

This counts:

• Numbers divisible by 5 (contribute one 5)
• Numbers divisible by 25 (contribute an extra 5)
• Numbers divisible by 125 (contribute yet another 5)
• And so on...

Approach 1: Brute Force (Linear Search)

Intuition

Start from n = 1 and increment, calculating trailing zeroes for each factorial until we find one with at least n trailing zeroes.

Algorithm

1. Start with x = 0
2. Increment x and calculate trailingZeroes(x!)
3. Return first x where trailingZeroes(x!) >= n

public class Solution {
    private long countTrailingZeroes(long num) {
        long count = 0;
        long power = 5;
        
        while (power <= num) {
            count += num / power;
            power *= 5;
        }
        
        return count;
    }
    
    public long smallestWithNZeroes(long n) {
        long x = 0;
        
        while (countTrailingZeroes(x) < n) {
            x++;
        }
        
        return x;
    }
}

Complexity Analysis

• Time Complexity: O(n × log₅n) - Linear search up to roughly 5n, each check takes O(log₅n)
• Space Complexity: O(1)

Approach 2: Binary Search (Optimal)

Intuition

The function trailingZeroes(x!) is monotonically non-decreasing. This allows us to binary search for the smallest x where trailingZeroes(x!) >= n.

Key Observations:

1. If x! has k trailing zeroes, (x+1)! has at least k trailing zeroes
2. For every 5 numbers, trailing zeroes increase by at least 1
3. Upper bound: 5n (roughly, since every 5 numbers adds at least one 5)
4. Binary search for the smallest valid x

Algorithm

1. Set low = 0, high = 5n (upper bound)
2. Binary search for smallest x where trailingZeroes(x) >= n
3. Return the result

public class TrailingZeroes {
    private long countTrailingZeroes(long num) {
        long count = 0;
        long power = 5;
        
        while (power <= num) {
            count += num / power;
            power *= 5;
        }
        
        return count;
    }
    
    public long smallestWithNZeroes(long n) {
        // Edge case
        if (n == 0) return 0;
        
        long low = 0;
        long high = 5 * n;  // Upper bound
        long result = high;
        
        while (low <= high) {
            long mid = low + (high - low) / 2;
            long zeroes = countTrailingZeroes(mid);
            
            if (zeroes >= n) {
                result = mid;
                high = mid - 1;  // Try smaller
            } else {
                low = mid + 1;   // Need larger
            }
        }
        
        return result;
    }
    
    public static void main(String[] args) {
        TrailingZeroes tz = new TrailingZeroes();
        System.out.println(tz.smallestWithNZeroes(1));   // Output: 5
        System.out.println(tz.smallestWithNZeroes(2));   // Output: 10
        System.out.println(tz.smallestWithNZeroes(6));   // Output: 25
        System.out.println(tz.smallestWithNZeroes(25));  // Output: 100
    }
}

Dry Run Example

Why Upper Bound is 5n?

For a number x:

• Every 5 numbers contribute at least 1 factor of 5
• So x/5 is a lower bound on trailing zeroes
• For x = 5n: zeroes >= n
• This guarantees we find an answer within [0, 5n]

Complexity Analysis

• Time Complexity: O(log(5n) × log₅(5n)) = O(log²n)
  • Binary search: O(log(5n)) iterations
  • Each countTrailingZeroes: O(log₅(5n))
• Space Complexity: O(1)

Important Note: Gap in Trailing Zeroes

Not every number of trailing zeroes is achievable. For example, there's no x where x! has exactly 5 trailing zeroes.

So if asked for "exactly n trailing zeroes", the problem might have no solution for certain n values.

Variant: Check if Exact Count Exists

Key Takeaways

1. Trailing Zeroes Formula: Count factors of 5 using Σ floor(n/5^i)
2. Monotonic Property: trailingZeroes is non-decreasing, enabling binary search
3. Upper Bound: 5n is sufficient since each 5 numbers adds at least one zero
4. Gaps Exist: Not all trailing zero counts are achievable (e.g., 5, 11, 17...)
5. Binary Search Pattern: Search for "first x satisfying condition"
6. Time Complexity: O(log²n) is much better than O(n × log₅n) brute force
7. Overflow Warning: Use long long for large inputs (n up to 10^9)