Preimage Size of Factorial Zeroes Function

lcpy gen -n 793   # by problem number
lcpy gen -s preimage_size_of_factorial_zeroes_function   # by problem name

Input: k = 0
Output: 5
Explanation: 0!, 1!, 2!, 3!, and 4! end with k = 0 zeroes.

Input: k = 5
Output: 0
Explanation: There is no x such that x! ends in k = 5 zeroes.

Input: k = 3
Output: 5

class Solution:
    # Time: O(log^2 k)
    # Space: O(1)
    def preimage_size_fzf(self, k: int) -> int:
        def zeroes(x: int) -> int:
            count = 0
            power = 5
            while power <= x:
                count += x // power
                power *= 5
            return count

        def first_with_at_least(target: int) -> int:
            low, high = 0, 5 * (target + 1)
            while low < high:
                mid = (low + high) // 2
                if zeroes(mid) >= target:
                    high = mid
                else:
                    low = mid + 1
            return low

        left = first_with_at_least(k)
        if zeroes(left) != k:
            return 0
        return first_with_at_least(k + 1) - left