793 Preimage Size of Factorial Zeroes Function

793. Preimage Size of Factorial Zeroes Function

1. Question

Letf(x)be the number of zeroes at the end ofx!. (Recall thatx! = 1 * 2 * 3 * ... * x, and by convention,0! = 1.)

For example,f(3) = 0because 3! = 6 has no zeroes at the end, whilef(11) = 2because 11! = 39916800 has 2 zeroes at the end. GivenK, find how many non-negative integersxhave the property thatf(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:

• Kwill 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]

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)