Preimage Size of Factorial Zeroes Function

Hard
716.

Preimage Size of Factorial Zeroes Function

Preimage Size of Factorial Zeroes Function is a hard coding problem on math, binary search and number theory, asked in Amazon, Google and Meta interviews.

Let f(x) be the number of trailing zeros in x!. For instance f(3) = 0 because 3! = 6, and f(11) = 2 because 11! = 39916800.

Given k, return how many non-negative integers x satisfy f(x) == k.

Example 1

Input
k = 0
Output
5
Explanation
f(x) = 0 for x in {0, 1, 2, 3, 4}.

Example 2

Input
k = 5
Output
0
Explanation
f jumps from 4 (at x = 20…24) to 6 (at x = 25), skipping 5 entirely.

Example 3

Input
k = 3
Output
5
Explanation
f(x) = 3 for x in {15, …, 19}.

Constraints

  • 0 <= k <= 1000000000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} k
 * @return {number}
 */
var preimageSizeFZF = function(k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Preimage Size of Factorial Zeroes Function — Solution

Preimage Size of Factorial Zeroes Function solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Preimage Size of Factorial Zeroes Function is a hard coding problem on math, binary search and number theory, asked in Amazon, Google and Meta interviews.

Problem statement

Let f(x) be the number of trailing zeros in x!. For instance f(3) = 0 because 3! = 6, and f(11) = 2 because 11! = 39916800.

Given k, return how many non-negative integers x satisfy f(x) == k.

Example 1

Input: k = 0
Output: 5
Explanation: f(x) = 0 for x in {0, 1, 2, 3, 4}.

Example 2

Input: k = 5
Output: 0
Explanation: f jumps from 4 (at x = 20…24) to 6 (at x = 25), skipping 5 entirely.

Example 3

Input: k = 3
Output: 5
Explanation: f(x) = 3 for x in {15, …, 19}.

Constraints

  • 0 <= k <= 1000000000

Hints for Preimage Size of Factorial Zeroes Function

  1. Hint 1

    f(x) = x/5 + x/25 + x/125 + … — count the factors of five, since twos are always plentiful.

  2. Hint 2

    f is non-decreasing and rises only at multiples of 5, always by at least one and sometimes by more.

  3. Hint 3

    So the answer is only ever 5 or 0: binary search for the smallest x with f(x) >= k and check whether it lands exactly on k.

How to solve Preimage Size of Factorial Zeroes Function

f is a step function that is constant on each block of five consecutive integers and jumps at every multiple of 5. So each value it attains is attained exactly five times, and values it skips are attained zero times.

Approach

  1. Implement f(x) as the Legendre sum x/5 + x/25 + x/125 + ….
  2. Binary search the smallest x >= 0 with f(x) >= k, using 5(k + 1) as a safe upper bound.
  3. Return 5 if f(x) == k, otherwise 0.

Why it works

Between consecutive multiples of 5 no new factor of five appears, so f is constant across each block of five. At a multiple of 5 it jumps by at least 1 — by more at multiples of 25 — which is exactly why some values of k are skipped. The upper bound works because f(5(k+1)) >= k + 1 > k.

Complexity

  • Time — O(log k · log k)
  • Space — O(1)

Pitfalls

  • The search space reaches about 5 × 10^9, which overflows a 32-bit integer — use 64-bit bounds.
  • p *= 5 also overflows if the loop is not stopped once p > x.
  • Answering 1 for a value that is attained ignores the five-wide plateau.

Reference solution

Python

def preimageSizeFZF(k: int) -> int:
    def zeros(x: int) -> int:
        total = 0
        p = 5
        while p <= x:
            total += x // p
            p *= 5
        return total

    lo, hi = 0, 5 * (k + 1)
    while lo < hi:
        mid = (lo + hi) // 2
        if zeros(mid) >= k:
            hi = mid
        else:
            lo = mid + 1
    return 5 if zeros(lo) == k else 0

Java

public static int preimageSizeFZF(int k) {
    long lo = 0, hi = 5L * (k + 1);
    while (lo < hi) {
        long mid = (lo + hi) / 2;
        if (trailingZeros(mid) >= k) hi = mid;
        else lo = mid + 1;
    }
    return trailingZeros(lo) == k ? 5 : 0;
}

static long trailingZeros(long x) {
    long total = 0, p = 5;
    while (p <= x) {
        total += x / p;
        p *= 5;
    }
    return total;
}

C++

static long long trailingZerosFZF(long long x) {
    long long total = 0, p = 5;
    while (p <= x) {
        total += x / p;
        p *= 5;
    }
    return total;
}

int preimageSizeFZF(int k) {
    long long lo = 0, hi = 5LL * (k + 1);
    while (lo < hi) {
        long long mid = (lo + hi) / 2;
        if (trailingZerosFZF(mid) >= k) hi = mid;
        else lo = mid + 1;
    }
    return trailingZerosFZF(lo) == k ? 5 : 0;
}

JavaScript

var preimageSizeFZF = function(k) {
    var zeros = function(x) {
        var total = 0, p = 5;
        while (p <= x) {
            total += Math.floor(x / p);
            p *= 5;
        }
        return total;
    };
    var lo = 0, hi = 5 * (k + 1);
    while (lo < hi) {
        var mid = Math.floor((lo + hi) / 2);
        if (zeros(mid) >= k) hi = mid;
        else lo = mid + 1;
    }
    return zeros(lo) === k ? 5 : 0;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue

Learn the technique: Binary Search