Smallest number with at least n trailing zeroes in factorial

The problem, simply

The factorial x! is 1 x 2 x 3 x ... x x. For example 5! = 120, which ends in one zero. Given n, find the smallest x such that x! ends in at least n zeros.

The factorial itself is far too big to compute. You need a way to count its zeros without building it.

A story to remember it

Picture it

Examples

Way 1: the simple way

Count zeros with the five rule, and try x = 0, 1, 2, ... until the count reaches n.

1. zeros(x) = x/5 + x/25 + x/125 + ... with whole number division. Each term counts the numbers that bring one more 5.
2. Start at x = 0 and add 1 until zeros(x) >= n.

class Solution {
    long zeros(long x) {
        long count = 0;
        for (long p = 5; p <= x; p *= 5) count += x / p;   // multiples of 5, 25, 125, ...
        return count;
    }

    public long smallest(long n) {
        long x = 0;
        while (zeros(x) < n) x++;
        return x;
    }
}

How long it takes: the answer is at most 5n, and each count takes O(log n) steps, so O(n log n). Extra room: O(1).

Way 2: the clever way

zeros(x) never goes down as x grows, so binary search for the first x with zeros(x) >= n.

Two facts make the search small:

• zeros(5n) >= n, because 5n / 5 alone is already n. So the answer is at most 5n.
• The count only changes at multiples of 5. So the answer is always a multiple of 5. Search over 5 x m for m from 1 to n.

1. lo = 1, hi = n. These are multipliers: the real number is 5 x m.
2. Take mid. If zeros(5 x mid) >= n, remember it and try smaller (hi = mid - 1). Otherwise try bigger (lo = mid + 1).
3. Return 5 x answer.

class Solution {
    long zeros(long x) {
        long count = 0;
        for (long p = 5; p <= x; p *= 5) count += x / p;
        return count;
    }

    public long smallest(long n) {
        if (n <= 0) return 0;
        long lo = 1, hi = n, answer = n;     // the answer is 5 * m for some m in 1..n
        while (lo <= hi) {
            long mid = lo + (hi - lo) / 2;
            if (zeros(5 * mid) >= n) {
                answer = mid;                // enough zeros: try smaller
                hi = mid - 1;
            } else {
                lo = mid + 1;                // too few: go bigger
            }
        }
        return 5 * answer;
    }
}

How long it takes: O(log n) guesses, each count O(log n), so O(log^2 n). Extra room: O(1).

Watch out for

• Counting 2s instead of 5s. There are always more 2s, so the 5s decide.
• Forgetting the extra 5 from 25, 125, and so on. x / 5 alone undercounts.
• Use long. 5 x n overflows int once n is above about 400 million.
• The plain search over 0..5n also works. Searching only multiples of 5 just makes the range 5 times smaller.

What interviewers ask next

• Count the trailing zeros of x! (LeetCode 172). That is zeros(x) alone, O(log x).
• How many x have exactly n trailing zeros (LeetCode 793)? The answer is always 0 or 5: find the first x with at least n and the first with at least n + 1, and subtract.
• Trailing zeros of x! in base b. Factor b into primes, count each prime in x! the same way (Legendre's formula), and divide by its power in b. The smallest result wins.
• The last nonzero digit of x! is a much harder follow up, solved by removing pairs of 2 and 5 and tracking the rest modulo 10.

Remember this

Grown-up words: the socks are the prime factors 2 and 5, the five rule is Legendre's formula, "never goes down" means monotonic, and guessing x is binary search on the answer.