# Preimage Size of Factorial Zeroes Function
**Difficulty:** HARD
[External](https://leetcode.com/problems/preimage-size-of-factorial-zeroes-function)
Canonical: https://scaleengineer.com/dsa/problems/preimage-size-of-factorial-zeroes-function
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
---
## Problem
Let `f(x)` be the number of zeroes at the end of `x!`. Recall that `x! = 1 * 2 * 3 * ... * x` and by convention, `0! = 1`.

* For example, `f(3) = 0` because `3! = 6` has no zeroes at the end, while `f(11) = 2` because `11! = 39916800` has two zeroes at the end.

Given an integer `k`, return the number of non-negative integers `x` have the property that `f(x) = k`.

**Example 1:**

**Input:** k = 0
**Output:** 5
**Explanation:** 0!, 1!, 2!, 3!, and 4! end with k = 0 zeroes.

**Example 2:**

**Input:** k = 5
**Output:** 0
**Explanation:** There is no x such that x! ends in k = 5 zeroes.

**Example 3:**

**Input:** k = 3
**Output:** 5

**Constraints:**

* `0 <= k <= 109`

# Approaches
## Brute Force by Linear Scan
This approach involves iterating through non-negative integers `x` starting from 0. For each `x`, we calculate `f(x)`, which is the number of trailing zeros in the factorial of `x`. We keep a count of how many times `f(x)` is equal to the given `k`. We can stop iterating once `f(x)` exceeds `k` because `f(x)` is a non-decreasing function.
**Time:** O(k * log k) - The number of trailing zeros `f(x)` is approximately `x/4`. So, to reach `k` zeros, `x` needs to be around `4k`. The loop runs up to `O(k)` times. Inside the loop, `countTrailingZeros(x)` takes `O(log_5 x)` or `O(log x)` time. Thus, the total complexity is `O(k * log k)`. · **Space:** O(1) - We only use a few variables to store the current number, its zero count, and the result.
**Pros:** Simple to understand and implement.; It is a direct translation of the problem statement.
**Cons:** The time complexity is proportional to `k`, which is too slow given the constraint `k <= 10^9`.; This approach will result in a 'Time Limit Exceeded' error on most online judges.
### Explanation
The number of trailing zeros in `x!` is determined by the number of times 5 is a factor in its prime factorization. This can be calculated using Legendre's formula: `f(x) = Σ floor(x / 5^i)` for `i` from 1 to infinity. We can implement a helper function `countZeros(x)` to compute this value. The main logic then iterates `x` from 0 upwards. In each step, it computes `f(x)` and compares it with `k`. If they are equal, a counter is incremented. The process terminates when `f(x)` surpasses `k`, as any larger `x` will also have more (or equal) zeros.

```java
class Solution {
    public int preimageSizeFZF(int k) {
        int resultCount = 0;
        long x = 0;
        while (true) {
            long zeros = countTrailingZeros(x);
            if (zeros == k) {
                resultCount++;
            } else if (zeros > k) {
                break;
            }
            // A small optimization: if we have found at least one solution and zeros > k,
            // we know the answer must be 5 or 0. If resultCount > 0, it must be 5.
            // But for a pure brute-force, we continue until zeros > k.
            if (resultCount > 0 && zeros > k) {
                return resultCount;
            }
            x++;
        }
        return resultCount;
    }

    private long countTrailingZeros(long x) {
        if (x < 0) {
            return 0;
        }
        long count = 0;
        for (long i = 5; x / i >= 1; i *= 5) {
            count += x / i;
        }
        return count;
    }
}
```
### Algorithm
*   Initialize a counter `count` to 0 and an integer `x` to 0.
*   Create a helper function, `countZeros(n)`, that computes the number of trailing zeros in `n!`. This is done by summing `floor(n/5) + floor(n/25) + floor(n/125) + ...`.
*   Start an infinite loop, incrementing `x` in each iteration.
*   Inside the loop, calculate `zeros = countZeros(x)`.
*   If `zeros` is equal to the target `k`, increment the `count`.
*   Since the function `f(x)` (number of zeros) is non-decreasing, if `zeros` becomes greater than `k`, no subsequent `x` will have `k` zeros. So, we can break the loop.
*   Finally, return the `count`.

## Binary Search for Existence
A major improvement over brute force is to use binary search. The function `f(x)` is monotonic (non-decreasing), which is a prerequisite for binary search. A key observation is that `f(x)` is constant for `x` in any interval `[5m, 5m+4]`. This means if there is one solution for `f(x) = k`, there must be exactly 5 consecutive solutions. Therefore, the problem simplifies to determining if *any* solution exists. We can use binary search to efficiently find if there is an `x` such that `f(x) = k`.
**Time:** O((log k)^2) - The binary search performs `O(log(5k)) = O(log k)` iterations. In each iteration, `countTrailingZeros` is called, which takes `O(log_5 x) = O(log k)` time, as `x` can be up to `O(k)`. · **Space:** O(1) - Constant extra space is used.
**Pros:** Very efficient with a logarithmic time complexity with respect to k.; The logic is a standard application of binary search on a monotonic function.
**Cons:** The time complexity, while good, can be slightly improved.; It relies on the property that the answer is either 0 or 5, which might not be immediately obvious.
### Explanation
We are searching for an integer `x` within a range such that `f(x) = k`. Since `f(x)` is non-decreasing, we can apply binary search on `x`. The search space for `x` can be estimated. `f(x)` is approximately `x/4`, so `x` is roughly `4k`. A safe upper bound like `5L * (k + 1)` will suffice. The binary search algorithm will try to find an `x` that results in exactly `k` zeros. If it finds one, we know the answer is 5. If the search space is exhausted without finding such an `x`, it means `f(x)` 'jumps' over the value `k` (e.g., from `k-1` to `k+1`), and no integer `x` produces `k` zeros. In that case, the answer is 0.

```java
class Solution {
    public int preimageSizeFZF(int k) {
        long low = 0;
        // f(x) is approx x/4, so x is approx 4k. 5k is a safe upper bound.
        // For k=0, x can be up to 4. 5*(0+1)=5 is a safe bound.
        long high = 5L * (k + 1);

        while (low <= high) {
            long mid = low + (high - low) / 2;
            long zeros = countTrailingZeros(mid);

            if (zeros == k) {
                return 5;
            } else if (zeros < k) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return 0;
    }

    private long countTrailingZeros(long x) {
        if (x < 0) return 0;
        long count = 0;
        for (long i = 5; x / i >= 1; i *= 5) {
            count += x / i;
        }
        return count;
    }
}
```
### Algorithm
*   The core idea is that the number of solutions for `f(x) = k` is either 0 or 5. We can use binary search to check if at least one solution exists.
*   Set up a binary search for `x` in a suitable range. A safe upper bound for `x` is `5 * (k + 1)` because `f(x)` grows roughly as `x/4`.
*   In each step of the binary search, take the middle element `mid` and calculate `zeros = f(mid)`.
*   If `zeros == k`, we have found a value of `x` for which `f(x) = k`. Based on our observation, this implies there are 5 such values. So, we can immediately return 5.
*   If `zeros < k`, it means `mid` is too small, and we need to search for a larger `x`. We update the search space to the right half: `low = mid + 1`.
*   If `zeros > k`, it means `mid` is too large, and we need to search for a smaller `x`. We update the search space to the left half: `high = mid - 1`.
*   If the binary search completes without finding any `x` where `f(x) == k`, it means no such `x` exists, and the number of solutions is 0. In this case, we return 0.

## Binary Search on a Reduced Problem
This approach further refines the binary search by transforming the problem into an equivalent, but simpler one. Instead of searching for `x` directly, we leverage the structure of `f(x)`. We know that if a solution exists, there must be a solution of the form `x = 5m`. The problem `f(x) = k` is thus equivalent to `f(5m) = k` for some integer `m`.
**Time:** O((log k)^2) - The binary search for `m` is on the range `[0, k]`, taking `O(log k)` steps. Each step computes `f(m)`, which takes `O(log m) = O(log k)` time. · **Space:** O(1) - Constant extra space is used.
**Pros:** Highly efficient with the same asymptotic complexity as the previous binary search approach but on a smaller search space `[0, k]` vs `[0, 5k]`.; The logic is very clean due to the strictly increasing nature of the function `g(m)` being searched.
**Cons:** Requires a mathematical transformation which might be slightly more complex to derive than a direct binary search.
### Explanation
Using the property `f(5m) = m + f(m)`, the problem of finding an `x` such that `f(x) = k` is reduced to finding an `m` such that `m + f(m) = k`. Let's define a new function `g(m) = m + f(m)`. We can prove that `g(m)` is strictly increasing: `g(m+1) - g(m) = (m+1 + f(m+1)) - (m + f(m)) = 1 + (f(m+1) - f(m))`. Since `f(m)` is non-decreasing, `f(m+1) - f(m) >= 0`, which means `g(m+1) - g(m) >= 1`. The strict monotonicity of `g(m)` guarantees that there can be at most one integer `m` for which `g(m) = k`. We can find this `m` (if it exists) using binary search on the range `[0, k]`. If such an `m` is found, the answer is 5; otherwise, it's 0.

```java
class Solution {
    public int preimageSizeFZF(int k) {
        // We are looking for m such that m + f(m) = k.
        // Since f(m) >= 0, m <= k. So we can search for m in [0, k].
        long low = 0, high = k;
        while (low <= high) {
            long m = low + (high - low) / 2;
            long val = m + countTrailingZeros(m);

            if (val == k) {
                return 5;
            } else if (val < k) {
                low = m + 1;
            } else {
                high = m - 1;
            }
        }
        return 0;
    }

    private long countTrailingZeros(long x) {
        if (x < 0) return 0;
        long count = 0;
        for (long i = 5; x / i >= 1; i *= 5) {
            count += x / i;
        }
        return count;
    }
}
```
### Algorithm
*   The problem is transformed into finding an integer `m` such that `m + f(m) = k`.
*   Let `g(m) = m + f(m)`. This function is strictly increasing, which means for any `k`, there is at most one `m` that satisfies the equation.
*   We can use binary search to find this `m`.
*   The search space for `m` is `[0, k]`, because `m <= m + f(m) = k`.
*   In each step of the binary search, take the middle element `mid_m` and calculate `val = mid_m + f(mid_m)`.
*   If `val == k`, we have found the unique `m`. This implies a solution exists, so we return 5.
*   If `val < k`, we need a larger `m`, so we search in the right half: `low = mid_m + 1`.
*   If `val > k`, `mid_m` is too large, so we search in the left half: `high = mid_m - 1`.
*   If the loop finishes without finding a match, no such `m` exists, and we return 0.

# Solutions
### Java

```java
class Solution {
public
  int preimageSizeFZF(int k) { return g(k + 1) - g(k); }
private
  int g(int k) {
    long left = 0, right = 5 * k;
    while (left < right) {
      long mid = (left + right) >> 1;
      if (f(mid) >= k) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return (int)left;
  }
private
  int f(long x) {
    if (x == 0) {
      return 0;
    }
    return (int)(x / 5) + f(x / 5);
  }
}

```

### CPP

```cpp
class Solution {
public:
  int preimageSizeFZF(int k) { return g(k + 1) - g(k); }
  int g(int k) {
    long long left = 0, right = 1ll * 5 * k;
    while (left < right) {
      long long mid = (left + right) >> 1;
      if (f(mid) >= k) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return (int)left;
  }
  int f(long x) {
    int res = 0;
    while (x) {
      x /= 5;
      res += x;
    }
    return res;
  }
};

```

### Python

```python
class Solution:
    def preimageSizeFZF(self, k: int) -> int: def f(x): if x == 0: return 0 return x // 5 + f(x // 5) def g(k): return bisect_left(range(5 * k), k, key=f) return g(k + 1) - g(k)

```