Hit the Lottery
Allen has \(n\) dollars in the bank and wants to withdraw all of it in cash. The bills have the values \(1\), \(5\), \(10\), \(20\), and \(100\) dollars.
What is the minimum number of bills Allen can receive?
Constraints:
- \(1 \le n \le 10^9\)
Input:
- One line: integer \(n\).
Output:
- One integer — the minimum number of bills.
Examples:
Input:
125
Output:
3
(\(125 = 100 + 20 + 5\).)
Input:
43
Output:
5
(\(43 = 20 + 20 + 1 + 1 + 1\).)
Solution
We use the greedy rule: take as many bills of the largest value as possible, then continue with the next value on the remaining amount.
Why does the greedy rule give the minimum? Take any way to pay with the minimum number of bills. It cannot contain:
- five \(1\) bills, because one \(5\) bill would replace them;
- two \(5\) bills, because one \(10\) bill would replace them;
- two \(10\) bills, because one \(20\) bill would replace them;
- five \(20\) bills, because one \(100\) bill would replace them.
So the bills smaller than \(100\) sum to at most \(4 \cdot 1 + 5 + 10 + 4 \cdot 20 = 99\). This means that the number of \(100\) bills must be exactly \(\lfloor n / 100 \rfloor\), which is what the greedy rule takes. In the same way, the bills smaller than \(20\) sum to at most \(19\), the bills smaller than \(10\) to at most \(9\), and the bills smaller than \(5\) to at most \(4\), so the greedy rule also takes the right number of every other bill.
With division, each value needs one step: we take \(n / v\) bills of value \(v\), and the remaining amount is \(n \bmod v\).
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int bills[5] = {100, 20, 10, 5, 1};
int count = 0;
for (int i = 0; i < 5; i++) {
count += n / bills[i]; // take as many of the largest bill as possible
n %= bills[i];
}
cout << count << "\n";
}