Đề bài
A cashier gives change using quarters (25¢), dimes (10¢), nickels (5¢) and pennies (1¢). Always using the largest coin that still fits gives the fewest coins for these values. Return how many coins are needed for cents.
Implement fewest_coins(cents).
Input
cents: The change owed in cents.
Output
Return the minimum number of coins.
Ràng buộc
0 ≤ cents ≤ 1,000,000
Ví dụ
Đầu vào:
cents = 41
Kết quả mong đợi:
expected = 4Đầu vào:
long long cents = 41;
Kết quả mong đợi:
long long expected = 4;Đầu vào:
long cents = 41;
Kết quả mong đợi:
long expected = 4;Giải thích
One quarter (25), one dime (35), one nickel (40) and one penny (41): 4 coins.
Đầu vào:
cents = 0
Kết quả mong đợi:
expected = 0Đầu vào:
long long cents = 0;
Kết quả mong đợi:
long long expected = 0;Đầu vào:
long cents = 0;
Kết quả mong đợi:
long expected = 0;Giải thích
No change is owed: 0 coins.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Dùng mệnh giá lớn nhất có thể, rồi chuyển sang đồng nhỏ hơn với số tiền còn lại.
Gợi ý 2
Chia và lấy phần dư để đếm từng loại coin hiệu quả.
Gợi ý 3
Cẩn thận với bội số chính xác để không bỏ sót phần dư nào.
Độ phức tạp mong đợi
thời gian O(1), bộ nhớ phụ O(1)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.