1463. Zeros in Any Base
A calculator writes the factorial n! in base b and you want to know how many zeros appear at the end of that representation. Return that count as a long; note that 0! = 1, which has no trailing zero. Computing the factorial is impossible for large n, so factor b into primes p^e, compute the exponent of p in n! with Legendre's formula (n/p + n/p^2 + ... using integer division), and return the minimum over the primes of that exponent divided by e, rounded down. Intended cost is O(sqrt(b) + log n) time and O(1) space.
Example 1
- Input:
- n = 10, b = 10
- Output:
- 2
- Explanation:
10! = 3628800 ends in two zeros in base 10.
Example 2
- Input:
- n = 5, b = 10
- Output:
- 1
- Explanation:
5! = 120 ends in exactly one zero in base 10.
Constraints
0 ≤ n ≤ 1015
2 ≤ b ≤ 106
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 800 msC++ 200 msJava 400 msJavaScript 400 msTypeScript 400 ms
Expected complexity
- Time
- O(sqrt(b) + log n)
- Space
- O(1)