172. Factorial Trailing Zeroes
Description
Given an integer n
, return the number of trailing zeroes in n!
.
Note that n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1
.
Example 1:
Input: n = 3 Output: 0 Explanation: 3! = 6, no trailing zero.
Example 2:
Input: n = 5 Output: 1 Explanation: 5! = 120, one trailing zero.
Example 3:
Input: n = 0 Output: 0
Constraints:
0 <= n <= 104
Follow up: Could you write a solution that works in logarithmic time complexity?
Solutions
Solution 1: Mathematics
The problem is actually asking how many factors of $5$ are there in $[1,n]$.
Let's take $130$ as an example for analysis:
- Divide by $5$ for the first time, get $26$, indicating that there are $26$ numbers containing the factor $5$;
- Divide by $5$ for the second time, get $5$, indicating that there are $5$ numbers containing the factor $5^2$;
- Divide by $5$ for the third time, get $1$, indicating that there is $1$ number containing the factor $5^3$;
- Sum up to get the count of all factors of $5$ in $[1,n]$.
The time complexity is $O(\log n)$, and the space complexity is $O(1)$.
1 2 3 4 5 6 7 |
|
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 |
|
1 2 3 4 5 6 7 8 |
|