# LeetCode 793: Preimage Size of Factorial Zeroes Function

## Problem Restatement

Define:

```python
f(x)
```

as the number of trailing zeroes in:

```python
x!
```

We are given an integer `k`.

We need to return how many integers `x` satisfy:

```python
f(x) == k
```

This count is called the size of the preimage of `k`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer `k` |
| Output | Number of integers `x` such that `f(x) == k` |
| `f(x)` | Number of trailing zeroes in `x!` |
| Important property | The answer is always `0` or `5` |

Function shape:

```python
class Solution:
    def preimageSizeFZF(self, k: int) -> int:
        ...
```

## Examples

Example 1:

```python
k = 0
```

We compute:

| `x` | `x!` | Trailing zeroes |
|---:|---|---:|
| `0` | `1` | `0` |
| `1` | `1` | `0` |
| `2` | `2` | `0` |
| `3` | `6` | `0` |
| `4` | `24` | `0` |
| `5` | `120` | `1` |

Exactly five integers satisfy:

```python
f(x) == 0
```

So the answer is:

```python
5
```

Example 2:

```python
k = 5
```

There is no integer `x` such that:

```python
f(x) == 5
```

So the answer is:

```python
0
```

## First Thought: Compute Factorials

A direct idea is:

1. Compute factorials.
2. Count trailing zeroes.
3. Check which values produce exactly `k`.

This quickly becomes impossible because factorials grow extremely fast.

We need a mathematical property instead.

## Key Insight

Trailing zeroes in `x!` come from factors of:

```python
10 = 2 * 5
```

There are always more `2`s than `5`s in factorials, so the number of trailing zeroes equals the number of factors of `5`.

The standard formula is:

```python
f(x) = x // 5 + x // 25 + x // 125 + ...
```

For example:

```python
f(25) = 25 // 5 + 25 // 25
      = 5 + 1
      = 6
```

Now observe an important property.

The function `f(x)` is monotonic:

| `x` increases | `f(x)` |
|---|---|
| Larger `x` | Same or larger |

But `f(x)` sometimes jumps.

For example:

| `x` | `f(x)` |
|---:|---:|
| `24` | `4` |
| `25` | `6` |

The value `5` is skipped completely.

So some `k` values have no solutions.

When a solution exists, there are always exactly five consecutive values of `x`.

## Why Exactly Five?

Suppose:

```python
f(x) == k
```

Then:

```python
f(x + 1)
f(x + 2)
f(x + 3)
f(x + 4)
```

usually remain the same until the next multiple of `5`.

So solutions appear in blocks of five.

Therefore, the answer is only:

| Case | Answer |
|---|---|
| `k` appears in `f(x)` | `5` |
| `k` does not appear | `0` |

So we only need to check whether some `x` satisfies:

```python
f(x) == k
```

## Binary Search

Since `f(x)` is monotonic, we can binary search for the smallest `x` such that:

```python
f(x) >= k
```

Call this value:

```python
left_bound(k)
```

Then:

| Expression | Meaning |
|---|---|
| `left_bound(k)` | First `x` with `f(x) >= k` |
| `left_bound(k + 1)` | First `x` with `f(x) >= k + 1` |

The number of integers satisfying:

```python
f(x) == k
```

is:

```python
left_bound(k + 1) - left_bound(k)
```

This difference is always `0` or `5`.

## Algorithm

Define a helper:

```python
count_zeroes(x)
```

which computes trailing zeroes in `x!`.

Then define:

```python
left_bound(target)
```

using binary search.

Finally return:

```python
left_bound(k + 1) - left_bound(k)
```

## Correctness

The number of trailing zeroes in `x!` equals the number of factors of `5` in the factorial expansion. Therefore:

```python
f(x) = x // 5 + x // 25 + x // 125 + ...
```

correctly computes the trailing zero count.

The function `f(x)` is monotonic because increasing `x` adds more factors to the factorial and cannot decrease the number of trailing zeroes.

For a target `k`, `left_bound(k)` returns the smallest integer `x` such that:

```python
f(x) >= k
```

Similarly, `left_bound(k + 1)` returns the smallest integer where:

```python
f(x) >= k + 1
```

Therefore, every integer in the interval:

```python
[left_bound(k), left_bound(k + 1))
```

satisfies:

```python
f(x) == k
```

and no other integers do.

So the size of the preimage is exactly:

```python
left_bound(k + 1) - left_bound(k)
```

which the algorithm returns.

## Complexity

Let `M` be the binary search range.

| Metric | Value | Why |
|---|---|---|
| Time | `O(log M * log M)` | Binary search calls `count_zeroes`, which itself runs in logarithmic time |
| Space | `O(1)` | Only integer variables are used |

A safe upper bound is:

```python
5 * (k + 1)
```

because each multiple of `5` contributes at least one trailing zero.

## Implementation

```python
class Solution:
    def preimageSizeFZF(self, k: int) -> int:
        def count_zeroes(x: int) -> int:
            total = 0

            while x > 0:
                x //= 5
                total += x

            return total

        def left_bound(target: int) -> int:
            left = 0
            right = 5 * (target + 1)

            while left < right:
                mid = (left + right) // 2

                if count_zeroes(mid) < target:
                    left = mid + 1
                else:
                    right = mid

            return left

        return left_bound(k + 1) - left_bound(k)
```

## Code Explanation

The helper computes trailing zeroes:

```python
def count_zeroes(x: int) -> int:
```

Each division counts how many numbers contribute extra factors of `5`:

```python
x //= 5
total += x
```

The binary search finds the first value where:

```python
f(x) >= target
```

If the current midpoint has too few zeroes:

```python
if count_zeroes(mid) < target:
    left = mid + 1
```

Otherwise, we move leftward to find the first valid position:

```python
else:
    right = mid
```

Finally, the number of exact matches is:

```python
left_bound(k + 1) - left_bound(k)
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.preimageSizeFZF(0) == 5
    assert s.preimageSizeFZF(1) == 5
    assert s.preimageSizeFZF(2) == 5
    assert s.preimageSizeFZF(3) == 5
    assert s.preimageSizeFZF(4) == 5

    assert s.preimageSizeFZF(5) == 0

    assert s.preimageSizeFZF(6) == 5

    assert s.preimageSizeFZF(10) == 5
    assert s.preimageSizeFZF(11) == 0

    print("all tests passed")

run_tests()
```

Test coverage:

| Test | Why |
|---|---|
| `k = 0` | Smallest valid preimage |
| `k = 1..4` | Normal five-value blocks |
| `k = 5` | First skipped value |
| `k = 6` | First value after a jump |
| Larger skipped values | Confirms jump behavior |