793. Preimage Size of Factorial Zeroes Function

Version #2 Binary Search Result improved version
In my last solution, I binary searched the input twice, one for the first occurrence and for the last occurrence. There's some duplicate code
The question can be transformed into -> find the first occurrence for K and first occurrence for K+1
result would be [left, right)
Warning!!!!!!!!
 In this case, we are not looking for left/right whose trailing zeros equals exactly K
we are looking for the range where
left = (trailing zeros >= K)
right = (trailing zeros >= K + 1)
Other wise, if we are searching for exact K, for K = 16 the result exists, but for K = 17, it doesn't exists so returns -1, then the result would be totally wrong


class Solution {
    public int preimageSizeFZF(int K) {
// binary search for two times, 1st time find the 1st integer with trailing zeros count of K, 2nd time find the last
long left = binarySearch(K);
return left == -1 ? 0 : (int) (binarySearch(K + 1) - left);
}

private long binarySearch(int K) {
long start = 0;
long end = Long.MAX_VALUE;
while (start < end) {
long mid = start + (end - start) / 2;
long count = trailingZeroes(mid);
// System.out.println(mid + " count: " + count);
if (count < K) {
start = mid + 1;
} else {
end = mid;
}
}
return start;
}

public long trailingZeroes(long n) {
// given a number, how can we calculate trailing zeros of its factorial
// e.g. 10 -> 1 2 3 4 5 6 7 8 9 10 -> 5(2) -> 2
//      25 -> 1..5..10..15..20..25 -> 5(5) + 25(1) -> although in 25 we have two 5s, one of them is already counted in count of 5s
// so every time we count how many 5,25,125... are their less than num, and add them together
long counter = 0;
while (n > 0) {
counter += n / 5;
n /= 5;
}
return counter;
}
}


Version #1 Binary Search Result
I think the question description has defect, the statement saying that "find how many non-negative integers x have the property that f(x) = K"
But actually in the test case of 1000000000, it is counting results that are in long range


class Solution {
    public int preimageSizeFZF(int K) {
// binary search for two times, 1st time find the 1st integer with trailing zeros count of K, 2nd time find the last
Map<Long, Long> map = new HashMap<>();
long left = binarySearch(K, map);
if (left == -1) return 0;
// System.out.println("left " + left);
long right = binarySearch2(K, map);
// System.out.println("right " + right);
if (right != -1) { // [left, right]
return (int) (right - left + 1);
}
return 0;
}

private long binarySearch2(int K, Map<Long, Long> map) {
long start = 0;
long end = Long.MAX_VALUE;
while (start + 1 < end) { // in case of endless loop
long mid = start + (end - start) / 2;
long count = map.getOrDefault(mid, trailingZeroes(mid));

if (count > K) {
end = mid - 1;
} else if (count < K){
start = mid + 1;
} else {
start = mid;
}
}
if (trailingZeroes(end) == K) {
return end;
} else if (trailingZeroes(start) == K) {
return start;
} else {
return -1;
}
}

private long binarySearch(int K, Map<Long, Long> map) {
long start = 0;
long end = Long.MAX_VALUE;
while (start < end) {
long mid = start + (end - start) / 2;
long count = trailingZeroes(mid);
// System.out.println(mid + " count: " + count);
map.put(mid, count);
if (count < K) {
start = mid + 1;
} else {
end = mid;
}
}
return trailingZeroes(start) == K ? start : -1;
}

public long trailingZeroes(long n) {
// given a number, how can we calculate trailing zeros of its factorial
// e.g. 10 -> 1 2 3 4 5 6 7 8 9 10 -> 5(2) -> 2
//      25 -> 1..5..10..15..20..25 -> 5(5) + 25(1) -> although in 25 we have two 5s, one of them is already counted in count of 5s
// so every time we count how many 5,25,125... are their less than num, and add them together
long counter = 0;
while (n > 0) {
counter += n / 5;
n /= 5;
}
return counter;
}
}