Trailing Zeros ใน n!
ศูนย์ท้ายมาจาก factor 10 = 2 × 5 ใน factorial มี factor 2 มากกว่า 5 เสมอ → นับจำนวน factor 5
สูตร: Z(n) = ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + ...
ตัวอย่างโค้ด
public class Demo {
static int trailingZeros(int n) {
int count = 0;
for (int i = 5; n / i >= 1; i *= 5) {
count += n / i;
}
return count;
}
public static void main(String[] args) {
int n = 1_000_000;
System.out.println("Trailing zeros in " + n + "! = " + trailingZeros(n));
// Test cases
for (int test : new int[]{5, 10, 25, 100, 1000}) {
System.out.println(test + "! → " + trailingZeros(test) + " zeros");
}
}
}
ผลลัพธ์
Trailing zeros in 1000000! = 249998 5! → 1 zeros 10! → 2 zeros 25! → 6 zeros 100! → 24 zeros 1000! → 249 zeros
คำอธิบาย
- ทุก 5 ตัวมี factor 5 หนึ่งตัว → +1 zero
- ทุก 25 ตัวมี factor 5 เพิ่มอีก (25 = 5²) → +1 zero
- ทุก 125 ตัวเพิ่มอีก (125 = 5³) → +1 zero
- ... จนกว่า n/i < 1
Complexity
- Time: O(log₅ n) - loop ประมาณ log₅(n) รอบ
- Space: O(1)
- เร็วมาก: n=10⁹ ใช้แค่ ~13 iterations
ขยาย: หา Trailing Zeros ใน Base อื่น
Base b = p₁^e₁ × p₂^e₂ × ... หา factor pᵢ ใน n! แล้วหาร eᵢ หาค่า min
