Skip to content

793. Preimage Size of Factorial Zeroes Function

DifficultyHard

Description

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 two zeroes at the end.

Given an integer k, return the number of 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.

Example 3:

Input: k = 3
Output: 5

 

Constraints:

  • 0 <= k <= 109

Solutions

Solution 1

Thinking

\(f(x)\) is the trailing zeros of \(x!\). The preimage of \(k\) is empty when \(f\) skips \(k\), otherwise a run of \(x\) (usually length \(5\)).

\(g(k)\) is the least \(x\) with \(f(x)\ge k\); the answer is \(g(k+1)-g(k)\). Since \(f(x)\ge x/5\), binary-search \(g\) in \([0,5k]\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int preimageSizeFZF(int k) {
        return g(k + 1) - g(k);
    }

    private int g(int k) {
        long left = 0, right = 5 * k;
        while (left < right) {
            long mid = (left + right) >> 1;
            if (f(mid) >= k) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return (int) left;
    }

    private int f(long x) {
        if (x == 0) {
            return 0;
        }
        return (int) (x / 5) + f(x / 5);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int preimageSizeFZF(int k) {
        return g(k + 1) - g(k);
    }

    int g(int k) {
        long long left = 0, right = 1ll * 5 * k;
        while (left < right) {
            long long mid = (left + right) >> 1;
            if (f(mid) >= k) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return (int) left;
    }

    int f(long x) {
        int res = 0;
        while (x) {
            x /= 5;
            res += x;
        }
        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func preimageSizeFZF(k int) int {
    f := func(x int) int {
        res := 0
        for x != 0 {
            x /= 5
            res += x
        }
        return res
    }

    g := func(k int) int {
        left, right := 0, k*5
        for left < right {
            mid := (left + right) >> 1
            if f(mid) >= k {
                right = mid
            } else {
                left = mid + 1
            }
        }
        return left
    }

    return g(k+1) - g(k)
}

Comments