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 nonnegative 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 preimages 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.


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:
An Integer ‘k’: The input to the function is a nonnegative integer ‘k’. The problem requires us to find the number of nonnegative integers x for which the number of trailing zeroes in x! (factorial of x) is equal to ‘k’.
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.
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!.
Count of Nonnegative Integers ‘x’: The output of the function is the count of nonnegative 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:
The problem statement is asking for the count of nonnegative integers whose factorial ends with ‘k’ trailing zeroes.
‘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.
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:
We can solve this problem by performing a binary search. In each iteration, we calculate the number of trailing zeroes in the middle number.
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.
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:


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
 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 (IfElse): 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.
 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 (IfElse) (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.
 Problemsolving approach
The given problem is about finding a nonnegative 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 midpoint (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
 Pythonbased coding drills for identified concepts:
a. Function Definition:


b. Integer Division and Modulus:


c. Conditional Statement (IfElse):


d. Recursion:


e. Binary Search:


f. Return Statement:


 ProblemSpecific Drills:
a. Trailing Zeroes in a Factorial:


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.
 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 midpoint’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
.