นับศูนย์ท้าย (Trailing Zeros) ใน Factorial ด้วย Python

โจทย์: หาจำนวนศูนย์ต่อท้ายของ n! (Factorial)

หลักการ

ศูนย์ท้ายเกิดจากตัวประกอบ 10 = 2 × 5 ใน Factorial มีตัวประกอบ 2 มากกว่า 5 มาก ดังนั้นนับแค่ตัวประกอบ 5

จำนวน 5 ใน n! = ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + ...

ตัวอย่างโค้ด Python

def trailing_zeros(n):
    count = 0
    i = 5
    while n // i >= 1:
        count += n // i
        i *= 5
    return count

# ทดสอบ
n = 79
print(f"Count of trailing 0s in {n}! is {trailing_zeros(n)}")
# Output: 18

ผลลัพธ์

Count of trailing 0s in 79! is 18

การตรวจสอบ

import math
print(math.factorial(79))
# ... 18 ศูนย์ท้าย

ความซับซ้อน: Time O(log₅ n), Space O(1) - เร็วมากแม้ n จะใหญ่ (10⁹)