Preimage Size Of Factorial Zeroes Function - Leetcode Solution

Problem Statement:

Given an integer n, we define the factorial zeroes function f(x) to be the number of zeroes at the end of x!. (Recall that x! = 1 * 2 * ... * x, and by convention, 0! = 1.)

For example, f(10) = 2 because 10! = 3628800 has 2 zeroes at the end.

Given a number k, find the number of non-negative integers x less than or equal to k such that f(x) = n.

Example:

Input: n = 0, k = 0 Output: 1

Input: n = 5, k = 100 Output: 6 Explanation: 5! = 120, 10! = 3628800, 15! = 1307674368000, 20! = 2432902008176640000, 25! = 15511210043330985984000000, and 30! = 265252859812191058636308480000000, so f(x) = 5 for x = 5, 10, 15, 20, 25, 30.

Solution:

First, we have to understand that the number of trailing zeroes at the end of x! is equal to the number of times x is divisible by 5 plus the number of times x is divisible by 25 plus the number of times x is divisible by 125, and so on. Therefore, we can compute f(x) for any x by repeatedly dividing x by 5 until the quotient is less than 5, and accumulating the number of factors of 5.

With that in mind, we can use binary search to find the largest integer x such that f(x) < n, and the smallest integer y such that f(y) > n, and the answer to the problem is y - x - 1.

The reason we subtract one from y - x is because we want to count the number of integers x <= k, not including k, such that f(x) = n.

Here is the code implementing this solution:

class Solution: def preimageSizeFZF(self, n: int) -> int: lo, hi = 0, 5 * (n+1) while lo < hi: mid = (lo + hi) // 2 if self.trailingZeroes(mid) < n: lo = mid + 1 else: hi = mid x = lo

    lo, hi = 0, 5 * (n+1)
    while lo < hi:
        mid = (lo + hi) // 2
        if self.trailingZeroes(mid) <= n:
            lo = mid + 1
        else:
            hi = mid
    y = lo
    
    return y - x - 1

def trailingZeroes(self, n: int) -> int:
    cnt = 0
    while n > 0:
        cnt += n // 5
        n //= 5
    return cnt

Time Complexity: O(log(k)), since we use binary search to find x and y, and each search takes O(log(k)) time. The trailingZeroes function takes O(log(k)) time as well.

Space Complexity: O(1), since we only use constant extra space to store a few variables.

1