Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/793.html

793. Preimage Size of Factorial Zeroes Function (Hard)

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].

Companies:
Amazon

Solution 1.

// OJ: https://leetcode.com/problems/preimage-size-of-factorial-zeroes-function/
// Time: O((logK)^2)
// Space: O(1)
class Solution {
private:
    int getZeros(int i) {
        int ans = 0;
        while (i) {
            ans += i;
            i /= 5;
        }
        return ans;
    }
public:
    int preimageSizeFZF(int K) {
        if (!K) return 5;
        int i = 1;
        while (getZeros(i) < K) i *= 5;
        int L = i / 5, R = i;
        while (L <= R) {
            int M = (L + R) / 2;
            int z = getZeros(M);
            if (z == K) return 5;
            if (z < K) L = M + 1;
            else R = M - 1;
        }
        return 0;
    }
};

Java

  • class Solution {
    public int preimageSizeFZF(int K) {
        long low = 0, high = (long) K * 5;
        while (low <= high) {
            long mid = (high - low) / 2 + low;
            long endZeroes = endZeroes(mid);
            if (endZeroes == K)
                return 5;
            else if (endZeroes > K)
                high = mid - 1;
            else
                low = mid + 1;
        }
        return 0;
    }

    public long endZeroes(long num) {
        long zeroes = 0;
        while (num > 0) {
            num /= 5;
            zeroes += num;
        }
        return zeroes;
    }
}

  • // OJ: https://leetcode.com/problems/preimage-size-of-factorial-zeroes-function/
// Time: O((logK)^2)
// Space: O(1)
class Solution {
private:
    int getZeros(int i) {
        int ans = 0;
        while (i) {
            ans += i;
            i /= 5;
        }
        return ans;
    }
public:
    int preimageSizeFZF(int K) {
        if (!K) return 5;
        int i = 1;
        while (getZeros(i) < K) i *= 5;
        int L = i / 5, R = i;
        while (L <= R) {
            int M = (L + R) / 2;
            int z = getZeros(M);
            if (z == K) return 5;
            if (z < K) L = M + 1;
            else R = M - 1;
        }
        return 0;
    }
};

  • 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)

All Problems

All Solutions