สมมติว่าเรามีตัวเลข n เราต้องหาจำนวนที่น้อยที่สุด m โดยที่แฟคทอเรียลของ m มีจำนวน 0 เป็นอย่างน้อย n
ดังนั้นหากอินพุตเป็นเหมือน n =2 ผลลัพธ์จะเป็น 10 เพราะ 10! =3628800 และ 9! =362880 จำนวนขั้นต่ำที่มี 2 ศูนย์คือ 10
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนดฟังก์ชัน count_fives() นี่จะใช้เวลา n
- cnt :=0
- ในขณะที่ n> 0, ทำ
- n :=ชั้นของ (n / 5)
- cnt :=cnt + n
- คืนสินค้า
- จากวิธีหลัก ให้ทำดังต่อไปนี้ −
- ซ้าย :=1
- ขวา :=5^24
- ขณะขวา-ซ้าย> 5 ทำ
- กลาง :=ชั้นของ ((ขวา + ซ้าย) / 10) * 5
- ห้า :=count_fives(กลาง)
- ถ้า fives เหมือนกับ n แล้ว
- ขวา :=กลาง
- ซ้าย :=ขวา - 5
- ออกมาจากวงจร
- มิฉะนั้นเมื่อ fives
- ซ้าย :=กลาง
- มิฉะนั้น
- ขวา :=กลาง
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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)) อินพุต
2
ผลลัพธ์
10
