172. Factorial Trailing Zeroes
Tags:
Medium
Skills:
Math
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Số lượng số 0 ở cuối của n! đến từ việc nhân các cặp 2 và 5
Trong dãy số từ 1 → n, số lượng bội của 2 luôn nhiều hơn số lượng bội của 5, nên chỉ cần đếm số lần xuất hiện của 5 trong các thừa số của n!;
Tuy nhiên, các số như 25, 125,... đóng góp nhiều hơn một lần (vì 25 = 5 × 5, 125 = 5 × 5 × 5,...). Do đó, ta cần cộng thêm số lần các bội số lớn hơn của 5 xuất hiện.
Approach
zeroCount = 0 zeroCount , rồi cập nhật n = n // 5zeroCountTime and space compexity
Solution
1function trailingZeroes(n: number): number {
2 let zero_count = 0
3 while (n > 0) {
4 n = Math.floor(n / 5);
5 zero_count += n
6 }
7 return zero_count
8};