Problem statement

https://leetcode.com/problems/preimage-size-of-factorial-zeroes-function/

Solution

First, we can note, that number of ending zeroes in n! is [n/5] + [n/25] + ... . Then we can also notice that number of numbers ending with exactly k zeroes is either 0 or 5: because if (5t)! is ending with k zeroes, so are (5t+1)!, ..., (5t+4)!. But sometimes it can happen that there is a gap, for example for k = 5 there will be 0 numbers: 24! ends with 4 zeroes and 25! with 6 zeroes. So, number of zeroes is piece-wise increasing function, and we can perform binary search to find the place where number of zeroes is equal to K. If we find such a place, we return 5. If no, we return 0 in the end.

Complexity

Time complexity is O(log^2 K).

Code

class Solution:
    def preimageSizeFZF(self, K):
        def zeroes(num):
            cnt = 0
            while num:
                cnt += num // 5
                num //= 5
            return cnt
    
        beg, end = 0, 1<<32
        while beg < end:
            mid = (beg + end) // 2
            if zeroes(mid) == K: return 5
            if zeroes(mid) < K:
                beg = mid + 1
            else:
                end = mid - 1
                
        return 0

Remark

There is also nice O(log K) solution, but I think it is overkill.