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.
-
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; } } ############ 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); } }
-
// 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)
-
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) }