Preimage Size of Factorial Zeroes Function

Identifying Problem Isomorphism

“Preimage Size of Factorial Zeroes Function” (#793) can be approximately mapped to “Factorial Trailing Zeroes” (#172).

In “Preimage Size of Factorial Zeroes Function”, you are given an integer k and you need to find how many non-negative integers x have the property that f(x) = k, where f(x) is the number of trailing zeroes in x!.

In “Factorial Trailing Zeroes”, you are given an integer n and you have to return the number of trailing zeroes in n!. The main concept behind this problem is to count the number of factors of 5 in the factorial, as each factor of 5 contributes a trailing zero.

The reason for this mapping is that both problems deal with the number of trailing zeroes in the factorial of a number. While “Preimage Size of Factorial Zeroes Function” asks for the number of pre-images that result in a given number of trailing zeroes in their factorial, “Factorial Trailing Zeroes” uses this concept to determine the number of trailing zeroes in the factorial of a number.

“Factorial Trailing Zeroes” is simpler since it directly involves counting the factors of 5 in a given number’s factorial, while “Preimage Size of Factorial Zeroes Function” requires a deeper understanding of the mathematical concept and might involve binary search to find the preimages efficiently.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def preimageSizeFZF(self, k: int) -> int:
        def zeros(n):
            return n // 5 + zeros(n // 5) if n else 0

        l, r = 0, 10 * k + 1
        while l < r:
            m = (l + r) // 2
            if zeros(m) < k:
                l = m + 1
            else:
                r = m
        return 0 if zeros(l) != k else 5

Problem Classification

This problem falls under the Mathematical Computation domain and is related to Number Theory and Factorial computation. It requires an understanding of mathematical concepts and operations, specifically factorials, counting principles, and properties of numbers.

‘What’ Components:

  1. An Integer ‘k’: The input to the function is a non-negative integer ‘k’. The problem requires us to find the number of non-negative integers x for which the number of trailing zeroes in x! (factorial of x) is equal to ‘k’.

  2. Factorial Calculation: The problem requires an understanding of the factorial function, denoted by x!, which is the product of all positive integers less than or equal to x. For instance, 5! = 5 * 4 * 3 * 2 * 1 = 120.

  3. Zeroes at the End of Factorial: The problem centers around determining the number of trailing zeroes at the end of a factorial x!. A trailing zero is formed by a product of 10 = 2 * 5. So, we need to count the number of pairs of 2 and 5 in the prime factorization of x!.

  4. Count of Non-negative Integers ‘x’: The output of the function is the count of non-negative integers ‘x’ whose factorial has ‘k’ trailing zeroes.

This problem can be classified as a ‘Counting’ problem as it requires determining the count of numbers whose factorials end with ‘k’ zeroes. It also falls under the ‘Search’ problem category since we might need to search through potential values of ‘x’ to find the ones that satisfy the condition. Due to the involvement of factorials and prime factorization, it can also be categorized as a ‘Number Theory’ problem. Finally, due to potential large values of ‘k’, a naive approach might not be feasible and we may need to apply ‘Optimization’ techniques to solve the problem efficiently.

Thought Process

Problem Statement Cues:

  1. The problem statement is asking for the count of non-negative integers whose factorial ends with ‘k’ trailing zeroes.

  2. ‘k’ zeroes in the factorial number indicate that there are ‘k’ multiples of 10. Since 10 is the product of 2 and 5, we need ‘k’ multiples of 2 and 5 in the factorial’s prime factorization.

  3. However, in any factorial, the frequency of 2 as a prime factor is always more than the frequency of 5. So, we only need to count the multiples of 5.

Approach Direction:

  1. We can solve this problem by performing a binary search. In each iteration, we calculate the number of trailing zeroes in the middle number.

  2. If the number of trailing zeroes is less than ‘k’, then we search in the higher half of the search space. If the number of trailing zeroes is more than ‘k’, then we search in the lower half.

  3. To calculate the number of trailing zeroes in a number, we continually divide the number by 5 and add up the quotients until the number becomes 0.

Here is the Python3 code implementing the above approach:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def preimageSizeFZF(self, k: int) -> int:
        def zeros(n):
            return n // 5 + zeros(n // 5) if n else 0

        l, r = 0, 10 * k + 1
        while l < r:
            m = (l + r) // 2
            if zeros(m) < k:
                l = m + 1
            else:
                r = m
        return 0 if zeros(l) != k else 5

In the above code, we first define the helper function ‘zeros’ which returns the number of trailing zeroes in a given number’s factorial. In the ‘preimageSizeFZF’ function, we perform binary search between 0 and ‘10*k + 1’. In each iteration, we adjust our search space based on whether the middle number’s factorial has less or more than ‘k’ trailing zeroes. Finally, if the number of trailing zeroes in ’l’ is not equal to ‘k’, we return 0. Otherwise, we return 5 as there are 5 consecutive numbers whose factorial has the same number of trailing zeroes.

Language Agnostic Coding Drills

  1. Dissection of Code

Here are the distinct concepts in this code:

a. Function Definition: Defining a function to encapsulate a set of instructions.

b. Recursion: A recursive function is a function that calls itself during its execution.

c. Integer Division and Modulus: The // operator in Python divides and then rounds down to the nearest whole number.

d. Conditional Statement (If-Else): Control flow statements that allow code to be executed based on a certain condition.

e. Binary Search: A classic algorithm in computer science, binary search is used to find the location of a target value within a sorted array or list.

f. Return Statement: Used to exit a function and pass a value back to the caller.

  1. List of Coding Concepts or Drills

a. Function Definition (Easy): This is the most fundamental concept in any programming language. It’s used to define a block of code that performs a specific task.

b. Integer Division and Modulus (Easy): Another basic mathematical operation used in almost every programming task.

c. Conditional Statement (If-Else) (Easy to Medium): Used for decision making in programming, slightly more complex due to the logical component.

d. Recursion (Medium): A bit more complex, as it requires understanding how function calls work, and can lead to stack overflow if not carefully controlled.

e. Binary Search (Medium to Hard): This algorithm is a bit more complex as it requires a good understanding of the data structure (array or list) and how to work with indices. It also requires an understanding of the underlying logic and reasoning behind the algorithm.

f. Return Statement (Medium): Although the concept itself is easy, knowing when and what to return can be a bit tricky, especially in problems involving recursion or complex logical conditions.

  1. Problem-solving approach

The given problem is about finding a non-negative integer such that the number of trailing zeroes in its factorial is equal to a given number.

a. Begin by defining a helper function (zeros(n)) that calculates the number of trailing zeros in the factorial of n. This involves understanding factorials and the contribution of factors of 5 in creating trailing zeroes.

b. Implement a binary search between 0 and 10*k+1 to find the number that has exactly k trailing zeros in its factorial. If it exists, the number of trailing zeros for numbers 5 numbers away will be the same, hence return 5. If it doesn’t exist, return 0.

c. The binary search involves repeatedly dividing the search space in half, updating the bounds based on the comparison of k and the number of trailing zeros in the factorial of the mid-point (m).

This solution demonstrates the combination of binary search, recursion, and mathematical understanding to solve the problem. The result of each “drill” contributes to the final solution.

Targeted Drills in Python

  1. Python-based coding drills for identified concepts:

a. Function Definition:

1
2
3

def hello_world():
    print("Hello, World!")
hello_world()

b. Integer Division and Modulus:

1
2

print(10 // 3)  # Output: 3
print(10 % 3)   # Output: 1

c. Conditional Statement (If-Else):

1
2
3
4
5

x = 10
if x > 0:
    print("Positive number")
else:
    print("Non-positive number")

d. Recursion:

1
2
3
4
5
6
7

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

print(factorial(5))  # Output: 120

e. Binary Search:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1  # If not found

print(binary_search([1, 2, 3, 4, 5], 3))  # Output: 2

f. Return Statement:

1
2
3
4

def add(a, b):
    return a + b

print(add(5, 3))  # Output: 8
  1. Problem-Specific Drills:

a. Trailing Zeroes in a Factorial:

1
2
3
4
5
6
7
8

def trailing_zeros(n):
    count = 0
    while n > 0:
        n = n // 5
        count += n
    return count

print(trailing_zeros(10))  # Output: 2 (because 10! = 3628800 has two trailing zeroes)

This drill is essential for our problem because it calculates the number of trailing zeros in factorial of n, which is the core part of the problem.

  1. Assembling the Drills:

First, we would start by defining the helper function trailing_zeros(). Then, we would implement the binary search in the range [0, 10*k+1] using the trailing_zeros() function to compare the mid-point’s trailing zeros with k. If trailing_zeros(mid) < k, we move the left pointer to mid + 1, else we move the right pointer to mid. Finally, we check if trailing_zeros(left) == k, if so, return 5, else return 0.