> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/oj-practices/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/oj-practices/chapter1/binary-search/793-preimage-size-of-factorial-zeroes-function.md).

# 793     Preimage Size of Factorial Zeroes Function

## 793. [Preimage Size of Factorial Zeroes Function](https://leetcode.com/problems/preimage-size-of-factorial-zeroes-function/description/)

## 1. Question

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 2 zeroes at the end. Given`K`, find how many 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.
```

**Note:**

* `K`will be an integer in the range`[0, 10^9]`.

## 2. Implementation

**(1) Binary Search**

思路: 题目要求的是有多少个x，满足x!的值得0的个数等于K.

* 通过观察我们首先知道一个数的阶乘有多少个0取决于这个的有多少个5这个因子。numOfTrailingZeroes()可以让我们知道一个数末尾有多少个0。
* 如果一个数的末尾有K个0结尾，那么同样有K个0结尾的数**最多有5个**。原因很简单，如果x有K个0结尾，那么最多有 x + 1, x + 2, x + 3, x + 4也是K个零结尾，而对于x + 5，由于其比x多了一个5的因子，所以x + 5会有K + 1零结尾。
* 同时可以发现f(x) 是一个非递减函数，即如果 x < y, f(x) <= f(y)，这时我们想到用二分查找法找到符合条件的x，使得f(x) = K.， 查找x的范围在\[0, 5 \* K + 5]

```java
class Solution {
    public int preimageSizeFZF(int K) {
        long start = 0, end = 5L * (K + 1);

        while (start <= end) {
            long mid = start + (end - start) / 2;

            int count = numOfTrailingZeroes(mid);

            if (count < K) {
                start = mid + 1;
            }
            else if (count > K) {
                end = mid - 1;
            }
            else {
                return 5;
            }
        }
        return 0;
    }

    public int numOfTrailingZeroes(long num) {
        int count = 0;
        while (num > 0) {
            count += num / 5;
            num /= 5;
        }
        return count;
    }
}
```

## 3. Time & Space Complexity

**Binary Search**: 时间复杂度O((logK)^2), numOfTrailingZeroes()需要O(logK)的时间，在\[0, 5K + 5]的区间二分查找也需要O(logK)的时间。空间复杂度O(1)