We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Preimage Size of Factorial Zeroes Function

Number: 809

Difficulty: Hard

Paid? No

Companies: Adobe

Problem Description

Given an integer k, let f(x) be the number of trailing zeroes in x! (the factorial of x). The task is to determine how many non-negative integers x satisfy f(x) = k. For example, when k = 0, x can be 0, 1, 2, 3, or 4 since none of these factorials end with any zeroes.

Key Insights

  • The trailing zeros in x! are determined by the number of times 5 (and its powers) divide x!, as 2s are abundant.
  • f(x) can be computed by summing floor(x/5) + floor(x/25) + floor(x/125) + … until the division results in zero.
  • f(x) is a monotonic (non-decreasing) function, making binary search applicable.
  • Use binary search twice to determine the leftmost (first) and rightmost (last) x that satisfy f(x) = k. The count of valid x values is the size of this interval.
  • If no x exists such that f(x) equals k, then the result is 0.

Space and Time Complexity

Time Complexity: O(log(n)) per binary search call (n is chosen as 5*(k+1)), so overall O(log(n)). Space Complexity: O(1).

Solution

We solve the problem by first defining a helper function that calculates the number of trailing zeros in x!. Then, we use binary search to find the smallest x that yields exactly k trailing zeroes and likewise to find the largest x. The number of integers satisfying the condition is given by (right_boundary - left_boundary + 1). If no x meets the condition, we return 0. This approach exploits the monotonic nature of the trailing zero function for efficient searching.

Code Solutions

def trailingZeroes(x):
    # Calculate the number of trailing zeroes in x! by counting factors of 5
    count = 0
    while x:
        x //= 5
        count += x
    return count

def preimageSizeFZF(k):
    # Helper binary search routine to locate the boundary index where trailingZeroes(x) == k
    def binarySearch(target, findFirst):
        low, high = 0, 5 * (k + 1)  # Upper bound ensures we cover the region where f(x) might equal k
        res = -1
        while low <= high:
            mid = (low + high) // 2
            count = trailingZeroes(mid)
            if count < target:
                low = mid + 1
            elif count > target:
                high = mid - 1
            else:
                res = mid  # A valid candidate is found
                if findFirst:
                    high = mid - 1  # Continue searching left for the first occurrence
                else:
                    low = mid + 1   # Continue searching right for the last occurrence
        return res

    first = binarySearch(k, True)
    if first == -1:
        return 0  # No number x such that trailingZeroes(x) equals k
    last = binarySearch(k, False)
    return last - first + 1

# Example usage:
print(preimageSizeFZF(0))  # Output: 5
print(preimageSizeFZF(5))  # Output: 0
print(preimageSizeFZF(3))  # Output: 5
← Back to All Questions