Skip to main content
Talentd

Preimage Size of Factorial Zeroes Function - Solution & Explanation

HardMathBinary Search17 min readAsked at: Adobe
Practice this problem

Problem Statement

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 <= 109

Approach Overview

Problem Overview: Given an integer k, return how many non‑negative integers x satisfy f(x) = k, where f(x) is the number of trailing zeroes in x!. Trailing zeroes come from factors of 10 = 2 × 5, and factorials always contain more 2s than 5s, so the count depends on how many factors of 5 appear.

The trailing zero function is monotonic: as x increases, f(x) never decreases. This property allows search techniques instead of brute force enumeration.

Approach 1: Counting Trailing Zeroes using Iterative Increment (O(n log n) time, O(1) space)

Compute the factorial trailing zero count for successive values of x using the classic formula f(x) = x/5 + x/25 + x/125 .... Keep incrementing x and evaluate the zero count until it exceeds k. Track how many consecutive values produce exactly k. This works because trailing zeroes increase slowly, but scanning linearly becomes expensive when k is large. Each evaluation of f(x) costs O(log x) divisions, giving overall O(n log n) time.

Approach 2: Binary Search on Factorial Trailing Zeroes (O(log n · log n) time, O(1) space)

Use binary search on the range of possible x values. Because the trailing zero function is monotonic, you can search for the smallest x such that f(x) ≥ k. Do the same search for k + 1. The difference between the two positions gives the count of numbers whose factorial has exactly k trailing zeroes.

The helper function computes f(x) using repeated division by powers of 5, which comes directly from the mathematics of factorial prime factors. This step uses concepts from math and integer division properties. Each binary search takes O(log n) iterations and each evaluation of f(x) costs O(log n), leading to O(log² n) time overall.

An interesting property appears: the preimage size is always either 5 or 0. The binary search effectively detects whether a block of five consecutive integers maps to the same trailing zero count.

Recommended for interviews: Binary search on the trailing zero function. Interviewers expect you to recognize that f(x) is monotonic and searchable. The iterative scan demonstrates understanding of the factorial zero formula, but the binary search solution shows stronger algorithmic reasoning and scales to very large k.

Approach 1: Binary Search on Factorial Trailing Zeroes

The key to solving this problem is to realize that for any k, the values of x for which f(x) is constant form contiguous intervals. We can use binary search to find the boundaries of these intervals. The main task is to compute f(x), which gives us the number of trailing zeroes. For a given x, the trailing zeroes of x! can be found by calculating how many times 5 is a factor in numbers from 1 to x. This is given by:

f(x) = floor(x / 5) + floor(x / 25) + floor(x / 125) + ...

Use binary search to determine the first and last x such that f(x) = k.

This C solution first defines a helper function trailingZeroes to calculate the number of trailing zeroes in x!. The main function preimageSizeFZF uses binary search between 0 and 5*(k + 1) to find if any number produces exactly k trailing zeroes. If found, the range size is 5, reflecting the preimage size; otherwise, it's 0.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(log(k) * log(x)) where x is the maximum number such that f(x) = k.
Space Complexity: O(1).

Try this approach in the editor →

Approach 2: Counting Trailing Zeroes using Iterative Increment

A more direct, brute-force solution to finding the number of trailing zeroes is simply counting directly. Increment a counter and check how many numbers up to that point have exactly the desired number of trailing zeroes, using a straightforward f(x) calculation in each iteration. While less efficient than optimized approaches, this technique offers clarity and is best suited when k is small.

In this C approach, the function f is utilized in a brute force manner. It increments through integers, counting each one that matches the trailing zero requirement by calling itself and adjusting the count accordingly.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(N * log(x)), where N is the feasible range to be checked.
Space Complexity: O(1).

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Binary Search on Factorial Trailing Zeroes

Time Complexity: O(log(k) * log(x)) where x is the maximum number such that f(x) = k.
Space Complexity: O(1).

Counting Trailing Zeroes using Iterative Increment

Time Complexity: O(N * log(x)), where N is the feasible range to be checked.
Space Complexity: O(1).

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Counting Trailing Zeroes using Iterative IncrementO(n log n)O(1)Simple conceptual approach or when demonstrating the factorial trailing zero formula
Binary Search on Factorial Trailing ZeroesO(log² n)O(1)Preferred for interviews and large k because the trailing zero function is monotonic

Video Solution

Leetcode 793 Preimage Size of Factorial Zeroes Function • GET SDE READY • 1,858 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Preimage Size of Factorial Zeroes Function easy or hard?
LeetCode classifies this problem as Hard because it combines number theory with binary search on a derived monotonic function. Recognizing that the trailing zero function forms blocks of size five is the key insight that simplifies the final result.
Preimage Size of Factorial Zeroes Function Python/Java solution
Most implementations define a helper function that computes trailing zeroes using repeated division by 5. Then apply binary search to find the first value where the zero count reaches k and k+1. This approach works the same way in Python, Java, C++, C#, and JavaScript.
How to solve Preimage Size of Factorial Zeroes Function in O(n)?
A straightforward method iterates through increasing values of x and computes the trailing zero count using the formula x/5 + x/25 + x/125 and so on. Count how many x values produce exactly k trailing zeroes. This approach is easy to implement but slower than binary search for large inputs.
What is the best approach for Preimage Size of Factorial Zeroes Function?
Binary search on the factorial trailing zero function is the most efficient approach. The function f(x) = number of trailing zeroes in x! is monotonic, so you can binary search for the first x where f(x) >= k and the first x where f(x) >= k+1. The difference between these two positions gives the number of valid integers, typically 5 or 0.
Is Preimage Size of Factorial Zeroes Function asked at Google/Amazon/Meta?
Problems involving factorial trailing zeroes and binary search on monotonic functions frequently appear in interviews at companies like Google, Amazon, and Meta. The problem tests mathematical reasoning, binary search application, and understanding of factorial prime factorization.
What data structure is used in Preimage Size of Factorial Zeroes Function?
No special data structure is required. The solution relies on mathematical computation of trailing zeroes and a binary search over integer ranges. The key concept is the monotonic behavior of the trailing zero function.
What is the time complexity of Preimage Size of Factorial Zeroes Function?
The optimal binary search solution runs in O(log^2 n) time and O(1) space. Each binary search step takes O(log n) iterations, and computing the trailing zero count f(x) requires O(log n) divisions by powers of 5.

Ready to solve this problem?

Practice Preimage Size of Factorial Zeroes Function with our built-in code editor and test cases.

Practice on FleetCode
Previous

Factorial Trailing Zeroes