Jobs

Interviews

Discussions

Preimage Size of Factorial Zeroes Function

Hard

Asked by:

20 views

Topics:

Binary SearchGreedy Algorithms

Let f(x) be the number of zeroes at the end of x!. Recall that x! = 1 * 2 * 3 * ... * x and by convention, 0! = 1.

For example, f(3) = 0 because 3! = 6 has no zeroes at the end, while f(11) = 2 because 11! = 39916800 has two zeroes at the end.

Given an integer k, return the number of non-negative integers x have the property that f(x) = k.

Example 1:

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

Example 2:

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

Example 3:

Input: k = 3
Output: 5

Constraints:

0 <= k <= 10⁹

Try coding it in LeetCode

Preimage Size of Factorial Zeroes Function

Hard

Asked by:

20 views

Topics:

Binary SearchGreedy Algorithms

Let f(x) be the number of zeroes at the end of x!. Recall that x! = 1 * 2 * 3 * ... * x and by convention, 0! = 1.

For example, f(3) = 0 because 3! = 6 has no zeroes at the end, while f(11) = 2 because 11! = 39916800 has two zeroes at the end.

Given an integer k, return the number of non-negative integers x have the property that f(x) = k.

Example 1:

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

Example 2:

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

Example 3:

Input: k = 3
Output: 5

Constraints:

0 <= k <= 10⁹

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of possible values for k? Is there an upper bound?
If no integer n exists such that f(n) = k, what value should I return?
Is k guaranteed to be a non-negative integer?
Could you provide a small example to illustrate the expected behavior for a specific value of k?
Are you looking for the most efficient solution in terms of time complexity?

Brute Force Solution

Approach

To find out how many numbers have a factorial with a specific number of trailing zeroes, we could calculate the factorial of every number, count the zeroes, and see which numbers match. This is like trying every single possibility until we find our answer. We check each factorial and directly compare with what we are searching for.

Here's how the algorithm would work step-by-step:

Start with the number one.
Calculate the factorial of one.
Count the number of trailing zeroes in the calculated factorial.
Compare the number of trailing zeroes with the target number of zeroes we're looking for.
If they match, we found a number whose factorial has the desired number of zeroes. Keep track of it.
Repeat the process with the next number (two), then the next (three), and so on.
Continue this until we reach a point where the number of trailing zeroes consistently exceeds the target (because factorials and their trailing zeroes only increase or stay the same).
Count how many numbers had a factorial with the target number of trailing zeroes. This is the answer.

Code Implementation

def preimage_size_of_factorial_zeroes_function(target_zeroes):
    number = 0
    count = 0

    while True:
        factorial_zeroes = trailing_zeroes(number)

        # If we find a match, increment count.
        if factorial_zeroes == target_zeroes:
            count += 1

        # If we go over the target, break out.
        if factorial_zeroes > target_zeroes:

            break
        number += 1

    return count

def trailing_zeroes(number):
    zero_count = 0
    iterator = 5
    while iterator <= number:

        zero_count += number // iterator
        iterator *= 5
    return zero_count

Big(O) Analysis

Time Complexity

O(n!) – The algorithm iterates through numbers from 1 up to n, where n is not directly an input parameter, but the iteration continues until the number of trailing zeroes in the factorial consistently exceeds the target. For each number i in this iteration, the algorithm calculates i!. Calculating the factorial of i takes i-1 multiplications. While the loop doesn't necessarily run n times related to input k, the factorial calculation within the loop dominates the time complexity, causing it to grow factorially rather than polynomially with the increasing iterations. Therefore, the time complexity is approximately O(n!), where n is the iteration count which depends on how high the factorial needs to increase.

Space Complexity

O(1) – The provided solution keeps track of only one number whose factorial has the desired number of zeroes, along with the target number of zeroes. It does not create any auxiliary data structures that scale with the input. Therefore, the space used remains constant regardless of the input size and the algorithm has O(1) space complexity.

Optimal Solution

Approach

The most efficient way to find how many numbers have a factorial with a specific number of trailing zeros is to avoid calculating factorials directly. We can smartly use binary search to pinpoint the smallest and largest numbers that give us the target number of zeros, and then find the difference.

Here's how the algorithm would work step-by-step:

Understand that trailing zeros in a factorial are directly related to the number of times 5 appears as a factor in the numbers we're multiplying.
Realize that the number of trailing zeros in factorials is non-decreasing; that is, as the number increases, the number of trailing zeros either stays the same or increases.
Use binary search to find the smallest number whose factorial has *at least* the desired number of trailing zeros.
Use binary search again to find the smallest number whose factorial has *more than* the desired number of trailing zeros.
Subtract the first result from the second. The result is the number of integers whose factorial has exactly the desired number of trailing zeros.

Code Implementation

def preimage_size_of_factorial_zeroes_function(k_value):
    def trailing_zeroes(number):
        zero_count = 0
        power_of_five = 5
        while number >= power_of_five:
            zero_count += number // power_of_five
            power_of_five *= 5
        return zero_count

    def binary_search_smallest_number(target_zeroes):
        low_value = 0
        high_value = 5 * target_zeroes #Optimization: Reduce search space
        while low_value <= high_value:
            middle_value = (low_value + high_value) // 2
            zeroes = trailing_zeroes(middle_value)
            if zeroes < target_zeroes:
                low_value = middle_value + 1
            else:
                high_value = middle_value - 1
        return low_value

    # Find smallest 'x' where f(x) >= k
    lower_bound = binary_search_smallest_number(k_value)

    # Find smallest 'x' where f(x) >= k+1
    upper_bound = binary_search_smallest_number(k_value + 1)

    # The difference is the number of integers with exactly k trailing zeroes
    return upper_bound - lower_bound

Big(O) Analysis

Time Complexity

O(log n) – The algorithm employs binary search twice. Binary search works by repeatedly dividing the search interval in half. Given an input integer 'n' representing the target number of trailing zeros, both binary searches will converge on the target number in logarithmic time. Thus, both binary search operations contribute O(log n) time complexity. Therefore, the overall time complexity is dominated by the binary searches, resulting in O(log n).

Space Complexity

O(1) – The algorithm uses binary search twice, primarily manipulating integer variables to track search boundaries. It calculates the number of trailing zeros using a helper function, which also operates using a fixed number of integer variables. Therefore, the space required is independent of the input value (number of trailing zeros) and remains constant, involving only a few integer variables for binary search indices and counting zeros.

Edge Cases

Case	How to Handle
k is zero	The solution should return 5 since n = 0, 1, 2, 3, and 4 all have 0 trailing zeroes in their factorial.
k is a large number (e.g., close to the maximum integer value)	The solution must handle potentially large factorials and corresponding n values without causing integer overflow issues, possibly by using 64-bit integers or appropriate upper bounds in binary search.
k is negative	The problem specifies k is the desired number of trailing zeroes, which cannot be negative; therefore, it should either throw an exception or return 0.
The lower bound and upper bound for n converge to a value where f(n) is slightly different than k due to integer division imprecision.	The solution must carefully check the values near the binary search bounds to ensure that it correctly identifies the range of n values that result in exactly k trailing zeroes.
There is no n for the given k.	The solution should return 0 when there is no non-negative integer n such that f(n) == k (it can happen because the factorial zeroes function is a step function, and some values of k are skipped).
The calculation of trailing zeroes involves repeated division by 5; potential for inefficiencies if not implemented carefully.	Optimize the calculation of trailing zeroes to avoid unnecessary iterations, ensuring logarithmic time complexity with respect to n (the argument to the factorial function).
Large k where the required 'n' value to produce 'k' trailing zeroes exceeds the maximum representable integer.	If the binary search's upper bound calculation results in an integer overflow, then the algorithm should return 0 since we know no valid solution exists within representable number range.
Binary search implementation errors that cause infinite loops or incorrect results.	Ensure the binary search conditions (start <= end) and update logic (start = mid + 1, end = mid - 1) are correct to prevent infinite loops and find the exact start and end values for n.

k is zero

How to Handle:

The solution should return 5 since n = 0, 1, 2, 3, and 4 all have 0 trailing zeroes in their factorial.

k is a large number (e.g., close to the maximum integer value)

How to Handle:

The solution must handle potentially large factorials and corresponding n values without causing integer overflow issues, possibly by using 64-bit integers or appropriate upper bounds in binary search.

k is negative

How to Handle:

The problem specifies k is the desired number of trailing zeroes, which cannot be negative; therefore, it should either throw an exception or return 0.

The lower bound and upper bound for n converge to a value where f(n) is slightly different than k due to integer division imprecision.

How to Handle:

The solution must carefully check the values near the binary search bounds to ensure that it correctly identifies the range of n values that result in exactly k trailing zeroes.

There is no n for the given k.

How to Handle:

The solution should return 0 when there is no non-negative integer n such that f(n) == k (it can happen because the factorial zeroes function is a step function, and some values of k are skipped).

The calculation of trailing zeroes involves repeated division by 5; potential for inefficiencies if not implemented carefully.

How to Handle:

Optimize the calculation of trailing zeroes to avoid unnecessary iterations, ensuring logarithmic time complexity with respect to n (the argument to the factorial function).

Large k where the required 'n' value to produce 'k' trailing zeroes exceeds the maximum representable integer.

How to Handle:

If the binary search's upper bound calculation results in an integer overflow, then the algorithm should return 0 since we know no valid solution exists within representable number range.

Binary search implementation errors that cause infinite loops or incorrect results.

How to Handle:

Ensure the binary search conditions (start <= end) and update logic (start = mid + 1, end = mid - 1) are correct to prevent infinite loops and find the exact start and end values for n.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of possible values for k? Is there an upper bound?
If no integer n exists such that f(n) = k, what value should I return?
Is k guaranteed to be a non-negative integer?
Could you provide a small example to illustrate the expected behavior for a specific value of k?
Are you looking for the most efficient solution in terms of time complexity?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with the number one.
Calculate the factorial of one.
Count the number of trailing zeroes in the calculated factorial.
Compare the number of trailing zeroes with the target number of zeroes we're looking for.
If they match, we found a number whose factorial has the desired number of zeroes. Keep track of it.
Repeat the process with the next number (two), then the next (three), and so on.
Continue this until we reach a point where the number of trailing zeroes consistently exceeds the target (because factorials and their trailing zeroes only increase or stay the same).
Count how many numbers had a factorial with the target number of trailing zeroes. This is the answer.

Code Implementation

def preimage_size_of_factorial_zeroes_function(target_zeroes):
    number = 0
    count = 0

    while True:
        factorial_zeroes = trailing_zeroes(number)

        # If we find a match, increment count.
        if factorial_zeroes == target_zeroes:
            count += 1

        # If we go over the target, break out.
        if factorial_zeroes > target_zeroes:

            break
        number += 1

    return count

def trailing_zeroes(number):
    zero_count = 0
    iterator = 5
    while iterator <= number:

        zero_count += number // iterator
        iterator *= 5
    return zero_count

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Understand that trailing zeros in a factorial are directly related to the number of times 5 appears as a factor in the numbers we're multiplying.
Realize that the number of trailing zeros in factorials is non-decreasing; that is, as the number increases, the number of trailing zeros either stays the same or increases.
Use binary search to find the smallest number whose factorial has *at least* the desired number of trailing zeros.
Use binary search again to find the smallest number whose factorial has *more than* the desired number of trailing zeros.
Subtract the first result from the second. The result is the number of integers whose factorial has exactly the desired number of trailing zeros.

Code Implementation

def preimage_size_of_factorial_zeroes_function(k_value):
    def trailing_zeroes(number):
        zero_count = 0
        power_of_five = 5
        while number >= power_of_five:
            zero_count += number // power_of_five
            power_of_five *= 5
        return zero_count

    def binary_search_smallest_number(target_zeroes):
        low_value = 0
        high_value = 5 * target_zeroes #Optimization: Reduce search space
        while low_value <= high_value:
            middle_value = (low_value + high_value) // 2
            zeroes = trailing_zeroes(middle_value)
            if zeroes < target_zeroes:
                low_value = middle_value + 1
            else:
                high_value = middle_value - 1
        return low_value

    # Find smallest 'x' where f(x) >= k
    lower_bound = binary_search_smallest_number(k_value)

    # Find smallest 'x' where f(x) >= k+1
    upper_bound = binary_search_smallest_number(k_value + 1)

    # The difference is the number of integers with exactly k trailing zeroes
    return upper_bound - lower_bound

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
k is zero	The solution should return 5 since n = 0, 1, 2, 3, and 4 all have 0 trailing zeroes in their factorial.
k is a large number (e.g., close to the maximum integer value)	The solution must handle potentially large factorials and corresponding n values without causing integer overflow issues, possibly by using 64-bit integers or appropriate upper bounds in binary search.
k is negative	The problem specifies k is the desired number of trailing zeroes, which cannot be negative; therefore, it should either throw an exception or return 0.
The lower bound and upper bound for n converge to a value where f(n) is slightly different than k due to integer division imprecision.	The solution must carefully check the values near the binary search bounds to ensure that it correctly identifies the range of n values that result in exactly k trailing zeroes.
There is no n for the given k.	The solution should return 0 when there is no non-negative integer n such that f(n) == k (it can happen because the factorial zeroes function is a step function, and some values of k are skipped).
The calculation of trailing zeroes involves repeated division by 5; potential for inefficiencies if not implemented carefully.	Optimize the calculation of trailing zeroes to avoid unnecessary iterations, ensuring logarithmic time complexity with respect to n (the argument to the factorial function).
Large k where the required 'n' value to produce 'k' trailing zeroes exceeds the maximum representable integer.	If the binary search's upper bound calculation results in an integer overflow, then the algorithm should return 0 since we know no valid solution exists within representable number range.
Binary search implementation errors that cause infinite loops or incorrect results.	Ensure the binary search conditions (start <= end) and update logic (start = mid + 1, end = mid - 1) are correct to prevent infinite loops and find the exact start and end values for n.

k is zero

How to Handle:

The solution should return 5 since n = 0, 1, 2, 3, and 4 all have 0 trailing zeroes in their factorial.

k is a large number (e.g., close to the maximum integer value)

How to Handle:

k is negative

How to Handle:

The problem specifies k is the desired number of trailing zeroes, which cannot be negative; therefore, it should either throw an exception or return 0.

The lower bound and upper bound for n converge to a value where f(n) is slightly different than k due to integer division imprecision.

How to Handle:

The solution must carefully check the values near the binary search bounds to ensure that it correctly identifies the range of n values that result in exactly k trailing zeroes.

There is no n for the given k.

How to Handle:

The solution should return 0 when there is no non-negative integer n such that f(n) == k (it can happen because the factorial zeroes function is a step function, and some values of k are skipped).

The calculation of trailing zeroes involves repeated division by 5; potential for inefficiencies if not implemented carefully.

How to Handle:

Optimize the calculation of trailing zeroes to avoid unnecessary iterations, ensuring logarithmic time complexity with respect to n (the argument to the factorial function).

Large k where the required 'n' value to produce 'k' trailing zeroes exceeds the maximum representable integer.

How to Handle:

If the binary search's upper bound calculation results in an integer overflow, then the algorithm should return 0 since we know no valid solution exists within representable number range.

Binary search implementation errors that cause infinite loops or incorrect results.

How to Handle:

Ensure the binary search conditions (start <= end) and update logic (start = mid + 1, end = mid - 1) are correct to prevent infinite loops and find the exact start and end values for n.