Here, We see Preimage Size of Factorial Zeroes Function LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.
List of all LeetCode Solution
![Preimage Size of Factorial Zeroes Function LeetCode Solution](https://i0.wp.com/totheinnovation.com/wp-content/uploads/2024/02/LeetCode-Problem-Solution.png?resize=200%2C200&ssl=1)
Preimage Size of Factorial Zeroes Function LeetCode Solution
Table of Contents
Problem Statement
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
because3! = 6
has no zeroes at the end, whilef(11) = 2
because11! = 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
Preimage Size of Factorial Zeroes Function Leetcode Solution 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:
int trailingZeroes(long n) {
return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5);
}
};
Code language: PHP (php)
Preimage Size of Factorial Zeroes Function Leetcode Solution Java
class Solution {
public int preimageSizeFZF(int k) {
return (int)(rightBoundOfKTrailingZeros(k) - leftBoundOfKTrailingZeros(k) + 1);
}
private long leftBoundOfKTrailingZeros(int k) {
long start = 0;
long end = 5L * (k + 1);
while (start + 1 < end) {
long mid = start + (end - start) / 2;
if (trailingZeroes(mid) < k) {
start = mid;
} else {
end = mid;
}
}
if (trailingZeroes(start) == k) {
return start;
} else {
return end;
}
}
private long rightBoundOfKTrailingZeros(int k) {
long start = 0;
long end = 5L * (k + 1);
while (start + 1 < end) {
long mid = start + (end - start) / 2;
if (trailingZeroes(mid) <= k) {
start = mid;
} else {
end = mid;
}
}
if (trailingZeroes(end) == k) {
return end;
} else {
return start;
}
}
private int trailingZeroes(long n) {
int result = 0;
long divisor = 5;
while (divisor <= n) {
result += n / divisor;
divisor *= 5;
}
return result;
}
}
Code language: PHP (php)
Preimage Size of Factorial Zeroes Function Leetcode Solution JavaScript
var helper = function(m) {
let r = m;
while(m > 0) {
m = Math.floor(m / 5);
r += m;
}
return r;
}
var preimageSizeFZF = function(k) {
let min = 0, max = k+1;
while(min < max) {
let center = ~~((min+max)/2);
let zero = helper(center);
if (zero > k) {
max = center;
}
else if (zero < k) {
min = center + 1;
}
else {
return 5;
}
}
return 0;
};
Code language: JavaScript (javascript)
Preimage Size of Factorial Zeroes Function Solution Python
class Solution(object):
def preimageSizeFZF(self, k):
m = floor(log(4 * k + 1, 5))
while m:
unit = (5 ** m - 1) // 4
if k
return 0
k %= unit
m -= 1
return 5