How many ways to make change for a dollar?
US coins: penny (1 cent), nickel (5), dime (10), quarter (25) and half-dollar (50).
In how many different ways can you make exactly 100 cents using these coins? Two ways are the same if they use the same number of each coin.
Describe a method that a human could follow without listing hundreds of combinations by hand.
Show a hint
Organise by the largest coins first. For each choice of how many half-dollars and quarters, the remaining amount must be made from dimes, nickels and pennies, and that smaller count has a simple formula.
Your answer
Solving needs a free account
Answers, streaks and solutions unlock when you are signed in. Reading the question and the hint stays free.
Discussion
Sign in to join the discussion · reading is open to everyone
💡 Discussion rules
- No full solutions here. Hints and approaches only.
- Complexity, edge cases and intuition are the point.
- Interview experiences are welcome. Respect your NDAs.
Loading discussion…
Learn the concepts
The theory behind this question.
Related questions
Splitting a deck in the darkA hundred empty glasses and the dregsA painted cube cut into 27Which is right more often, a stopped clock or a slow one?Two people with exactly the same number of hairs
All questions →