โจทย์
พนักงานแคชเชียร์จะทอนเงินโดยใช้เหรียญควอเตอร์ (25¢), ไดม์ (10¢), นิเกิล (5¢) และเพนนี (1¢) เสมอ โดยเลือกเหรียญที่มีมูลค่าสูงสุดที่ยังสามารถใช้ได้ จะทำให้ใช้เหรียญจำนวนน้อยที่สุดสำหรับจำนวนเงินเหล่านี้ คืนค่าจำนวนเหรียญที่ต้องใช้สำหรับ cents.
ให้เขียนฟังก์ชัน fewest_coins(cents)
อินพุต
cents: จำนวนเงินทอนที่ต้องการในหน่วยเซนต์
เอาต์พุต
คืนค่าจำนวนเหรียญที่น้อยที่สุด
เงื่อนไข
0 ≤ cents ≤ 1,000,000
ตัวอย่าง
อินพุต:
cents = 41
ผลลัพธ์ที่คาดหวัง:
expected = 4อินพุต:
long long cents = 41;
ผลลัพธ์ที่คาดหวัง:
long long expected = 4;อินพุต:
long cents = 41;
ผลลัพธ์ที่คาดหวัง:
long expected = 4;คำอธิบาย
หนึ่งควอเตอร์ (25), หนึ่งไดม์ (35), หนึ่งนิเกิล (40) และหนึ่งเพนนี (41): รวม 4 เหรียญ
อินพุต:
cents = 0
ผลลัพธ์ที่คาดหวัง:
expected = 0อินพุต:
long long cents = 0;
ผลลัพธ์ที่คาดหวัง:
long long expected = 0;อินพุต:
long cents = 0;
ผลลัพธ์ที่คาดหวัง:
long expected = 0;คำอธิบาย
ไม่ต้องทอนเงิน: 0 เหรียญ
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
ใช้เหรียญที่มีมูลค่ามากที่สุดที่ใช้ได้ก่อน แล้วค่อยลดไปเหรียญที่เล็กลงตามจำนวนเงินที่เหลือ
คำใบ้ 2
ใช้การหารและหาเศษเพื่อให้นับเหรียญแต่ละชนิดได้อย่างมีประสิทธิภาพ
คำใบ้ 3
ระวังกรณีที่หารลงตัวพอดี จะได้ไม่เหลือเงินค้างโดยไม่ตั้งใจ
ความซับซ้อนที่คาดหวัง
เวลา O(1), หน่วยความจำเพิ่ม O(1)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน