โปรแกรมหาค่า m ที่ factorial m มีศูนย์ท้ายอย่างน้อย n ตัวใน Python

กำหนดจำนวน n หาค่า m ที่น้อยที่สุด ที่ factorial ของ m มีศูนย์ท้ายอย่างน้อย n ตัว

เช่น n = 2 ผลลัพธ์คือ 10 เพราะ 10! = 3628800 (มีศูนย์ 2 ตัว) ในขณะที่ 9! = 362880 (มีศูนย์ 1 ตัว)

วิธีแก้ปัญหา

• กำหนดฟังก์ชัน count_fives() รับ n คำนวณจำนวนตัวคูณ 5 ใน factorial
• cnt := 0
• while n > 0
  • n := floor(n / 5)
  • cnt := cnt + n
• คืนค่า cnt
• จาก main method
  • left := 1
  • right := 5^24
  • while right - left > 5
    • mid := floor((right + left) / 10) * 5
    • fives := count_fives(mid)
    • ถ้า fives == n
      • right := mid
      • left := right - 5
      • break
    • else if fives < n: left := mid
    • else: right := mid
  • คืนค่า right

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

def count_fives(n):
    cnt = 0
    while n > 0:
        n = n // 5
        cnt += n
    return cnt

def solve(n):
    left = 1
    right = 5**24
    while right - left > 5:
        mid = int((right + left) / 10) * 5
        fives = count_fives(mid)
        if fives == n:
            right = mid
            left = right - 5
            break
        elif fives < n:
            left = mid
        else:
            right = mid
    return right

n = 2
print(solve(n))

Input

2

Output

10