โจทย์
เศษส่วนที่มีตัวเศษเป็น 1 บางตัวเป็นทศนิยมรู้จบ (1/4 = 0.25) ส่วนที่เหลือเป็นทศนิยมซ้ำไม่รู้จบ เช่น 1/6 = 0.1666... ซ้ำเป็นชุดละ 1 หลัก และ 1/7 = 0.142857142857... ซ้ำเป็นชุดละ 6 หลัก ในบรรดา d = 2, 3, ..., limit ให้หา d ที่ 1/d มีชุดตัวเลขที่ซ้ำยาวที่สุด ให้เขียนโค้ดจำลองการหารยาวแบบที่ทำด้วยมือ ตัวเลขจะเริ่มซ้ำทันทีที่ได้เศษเดิมกลับมา
จงเขียนฟังก์ชัน longest_recurring_cycle(limit)
อินพุต
limit: ตัวส่วนที่มากที่สุดที่ต้องลอง
เอาต์พุต
คืนค่า d ที่มีชุดซ้ำยาวที่สุด เศษส่วนที่เป็นทศนิยมรู้จบถือว่ามีความยาวชุดซ้ำเป็น 0 ถ้ามีหลายค่าของ d ที่ยาวเท่ากัน ให้คืนค่าที่น้อยที่สุด
เงื่อนไข
2 ≤ limit ≤ 2000
ตัวอย่าง
อินพุต:
limit = 8
ผลลัพธ์ที่คาดหวัง:
expected = 7
อินพุต:
long long limit = 8;
ผลลัพธ์ที่คาดหวัง:
long long expected = 7;
อินพุต:
long limit = 8;
ผลลัพธ์ที่คาดหวัง:
long expected = 7;
คำอธิบาย
ความยาวชุดซ้ำของ 2 ถึง 8 คือ 0, 1, 0, 0, 1, 6, 0 คำตอบจึงเป็น 7
อินพุต:
limit = 5
ผลลัพธ์ที่คาดหวัง:
expected = 3
อินพุต:
long long limit = 5;
ผลลัพธ์ที่คาดหวัง:
long long expected = 3;
อินพุต:
long limit = 5;
ผลลัพธ์ที่คาดหวัง:
long expected = 3;
คำอธิบาย
1/3 ซ้ำหนึ่งหลัก ส่วน 1/2, 1/4 และ 1/5 เป็นทศนิยมรู้จบ คำตอบจึงเป็น 3
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
เลขโดดใหม่แต่ละตัวของ 1/d ได้จากเศษคูณด้วย 10
คำใบ้ 2
จำไว้ว่าเศษแต่ละค่าปรากฏครั้งแรกที่ขั้นตอนใด
คำใบ้ 3
ถ้าเศษเป็น 0 แสดงว่าเป็นทศนิยมรู้จบ มิฉะนั้นความยาวคาบคือระยะห่างระหว่างการพบเศษค่าเดิมสองครั้ง
ความซับซ้อนที่คาดหวัง
เวลา O(limit²), หน่วยความจำเพิ่ม O(limit)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน