793. Preimage Size of Factorial Zeroes Function LeetCode Solution
In this guide, you will get 793. Preimage Size of Factorial Zeroes Function LeetCode Solution with the best time and space complexity. The solution to Preimage Size of Factorial Zeroes Function problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Preimage Size of Factorial Zeroes Function
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
Complexity Analysis
Time Complexity: O(\log_2 K \cdot \log_5 K
Space Complexity:
793. Preimage Size of Factorial Zeroes Function LeetCode Solution in C++
class Solution {
public:
int preimageSizeFZF(int k) {
long l = 0;
long r = 5L * k;
while (l < r) {
const long m = (l + r) / 2;
if (trailingZeroes(m) >= k)
r = m;
else
l = m + 1;
}
return trailingZeroes(l) == k ? 5 : 0;
}
private:
// Same as 172. Factorial Trailing Zeroes
int trailingZeroes(long n) {
return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5);
}
}; /* code provided by PROGIEZ */
793. Preimage Size of Factorial Zeroes Function LeetCode Solution in Java
class Solution {
public int preimageSizeFZF(int k) {
long l = 0;
long r = 5 * (long) k;
while (l < r) {
final long m = (l + r) / 2;
if (trailingZeroes(m) >= k)
r = m;
else
l = m + 1;
}
return trailingZeroes(l) == k ? 5 : 0;
}
// Same as 172. Factorial Trailing Zeroes
private int trailingZeroes(long n) {
return n == 0 ? 0 : (int) (n / 5 + trailingZeroes(n / 5));
}
} // code provided by PROGIEZ
793. Preimage Size of Factorial Zeroes Function LeetCode Solution in Python
