There are exactly 9,823,546,661,906 ways to break $100. I…
1 reactions
There are exactly 9,823,546,661,906 ways to break $100.
I had some free time I wanted to know how many unique combinations could give change for $100, given an unlimited pool of a certain denomination or higher. For example, $100 = $50 + 2x$20 + $10 is 1 of 11 unique ways to give change using $10 bills or more. The good thing is if you're a bank carrying at least dimes you pretty much never have to worry about not having exact change.
The combinations grow roughly 100x for every denomination considered, so it took me forever to count them all. JK, I used a dynamic programming algorithm in Python3 and verified against small test cases. Results are rendered with Plotly.
#education
source
I had some free time I wanted to know how many unique combinations could give change for $100, given an unlimited pool of a certain denomination or higher. For example, $100 = $50 + 2x$20 + $10 is 1 of 11 unique ways to give change using $10 bills or more. The good thing is if you're a bank carrying at least dimes you pretty much never have to worry about not having exact change.
The combinations grow roughly 100x for every denomination considered, so it took me forever to count them all. JK, I used a dynamic programming algorithm in Python3 and verified against small test cases. Results are rendered with Plotly.
#education
source
1
| 4,000 mlx | |
| 5 | |
| 1 |