Dễ 1 đã giải Tỷ lệ chấp nhận 100.0%

Cash: Fewest Coins

Give change with as few U.S. coins as possible.

Bạn sẽ học được gì

  • Chọn đồng xu lớn nhất trước
  • Dùng chia nguyên và chia dư để đếm
  • Biết khi nào đổi tiền tham lam là tối ưu

Đề 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ụ

Ví dụ 1
Đầ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.

Ví dụ 2
Đầ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.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

# Người giải Ngôn ngữ Thời gian Bộ nhớ AI đánh giá Lời giải
1 HJhettory Jurash Python 873 ms - 4/5 Xem code

Học hỏi từ người khác

Giải pháp cộng đồng

Cảnh báo: Có 1 lời giải đầy đủ bên dưới Hãy thử tự giải trước. Bạn vẫn có thể xem mã của người khác và đánh giá AI. Đăng nhập và giải thử thách để tham gia thảo luận.