HardNo. 0793
Preimage Size of Factorial Zeroes Function — LeetCode 793 Python Solution
- Pattern
- Monotonic Stack
- Topics
- Math, Binary Search
- Reading time
- 2 min
- Source
- leetcode.com
The problem
Let f(x) be the number of zeroes at the end of x!. Recall that x!
Example
- Input
- k = 0
- Output
- 5
- Explanation
- 0!, 1!, 2!, 3!, and 4! end with k = 0 zeroes.
Python solution
class Solution:
def preimageSizeFZF(self, k: int) -> int:
def f(x):
if x == 0:
return 0
return x // 5 + f(x // 5)
def g(k):
return bisect_left(range(5 * k), k, key=f)
return g(k + 1) - g(k)Complexity
- Time
- O(log n) or O(n log n)
- Space · auxiliary
- O(1)
Pattern: Monotonic Stack
Answer "what is the next greater element" for every position in one pass. LeetCode 793. Preimage Size of Factorial Zeroes Function is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.
The monotonic stack guide has the Python template for the pattern and the 225 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0069 | Sqrt(x) | Easy |
| 0367 | Valid Perfect Square | Easy |
| 0400 | Nth Digit | Medium |
| 0441 | Arranging Coins | Easy |
| 0483 | Smallest Good Base | Hard |
| 0497 | Random Point in Non-overlapping Rectangles | Medium |
Frequently asked questions
- How hard is LeetCode 793. Preimage Size of Factorial Zeroes Function?
LeetCode 793. Preimage Size of Factorial Zeroes Function is rated Hard on LeetCode.
- What topics does LeetCode 793. Preimage Size of Factorial Zeroes Function cover?
LeetCode 793. Preimage Size of Factorial Zeroes Function is tagged Math and Binary Search on LeetCode.