> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Preimage Size of Factorial Zeroes Function

> Tested Python solution for LeetCode 793 with 28 pytest cases. Generate a practice environment with lcpy.

LeetCode 793, [Hard](/catalog/hard). Topics: [Math](/catalog/topics/math), [Binary Search](/catalog/topics/binary-search). [View on LeetCode](https://leetcode.com/problems/preimage-size-of-factorial-zeroes-function/description/).

Generate this problem as a practice environment: tested reference solution, 28 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 793   # by problem number
lcpy gen -s preimage_size_of_factorial_zeroes_function   # by problem name
```

## Problem

Let \<code>f(x)\</code> be the number of zeroes at the end of \<code>x!\</code>. Recall that \<code>x! = 1 \* 2 \* 3 \* ... \* x\</code> and by convention, \<code>0! = 1\</code>.

\<ul>
\<li>For example, \<code>f(3) = 0\</code> because \<code>3! = 6\</code> has no zeroes at the end, while \<code>f(11) = 2\</code> because \<code>11! = 39916800\</code> has two zeroes at the end.\</li>
\</ul>

\<p>Given an integer \<code>k\</code>, return \<em>the number of non-negative integers\</em> \<code>x\</code> \<em>have the property that\</em> \<code>f(x) = k\</code>.\</p>

### Examples

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

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

```
Input: k = 3
Output: 5
```

### Constraints

* 0 \<= k \<= 10^9

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/preimage_size_of_factorial_zeroes_function/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/preimage_size_of_factorial_zeroes_function/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(log^2 k)
    # Space: O(1)
    def preimage_size_fzf(self, k: int) -> int:
        def zeroes(x: int) -> int:
            count = 0
            power = 5
            while power <= x:
                count += x // power
                power *= 5
            return count

        def first_with_at_least(target: int) -> int:
            low, high = 0, 5 * (target + 1)
            while low < high:
                mid = (low + high) // 2
                if zeroes(mid) >= target:
                    high = mid
                else:
                    low = mid + 1
            return low

        left = first_with_at_least(k)
        if zeroes(left) != k:
            return 0
        return first_with_at_least(k + 1) - left
```

## Complexity

| Time | Space |
| - | - |
| O(log^2 k) | O(1) |

## Tags


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.