State your assumptions
The problem statement didn't specify the input and output formats, so document your choices. Personally, I would have chosen a fixed-point representation (e.g. a long
number of cents) for input rather than floating-point, and some form of "bag" structure (e.g. std::map<int,long>
representing value and quantity) for the output.
Unit tests - lots of them
You've included a single "happy-path" test, but I'd like to see a lot more.
What if P
> M
? Does P
== M
work correctly? What if P
and/or M
is ±infinity, or NaN?
The denominations don't need to be modifiable or local
The denominations
array can be constant:
static const int denominations[] = {1, 5, 10, 25, 50, 100};
Because it is superincreasing, it may simplify the code significantly to express it sorted in the reverse order, i.e. {100, 50, 25, 10, 5, 1}
, so that we can iterate over it in the natural order.
At some point, we'd be likely to pass it as a parameter (to allow for future changes to coinage, or use in other countries - e.g. in Scotland, we'd use {200, 100, 50, 20, 10, 5, 2, 1}
).
Improved version
#include <map>
using coin_bag = std::map<unsigned int, unsigned long>;
// Calculate the change from P-M as a bag of coins
// Empty result may mean M==P or an error condition such as underpayment.
// Otherwise, it's a map of coin value => number of coins
// Note: we make no attempt to avoid or detect integer overflow.
coin_bag getChange(long M, long P)
{
if (M <= P) {
// no change given
return {};
}
auto change = M - P;
static const auto denominations = {100, 50, 25, 10, 5, 1};
coin_bag coins;
for (auto c: denominations) {
auto q = change / c;
if (q > 0) {
coins[c] = q;
change -= c * q;
}
}
return coins;
}
// Test program
#include <iostream>
// helper
std::ostream& operator<<(std::ostream& os, const coin_bag& coins)
{
const char *sep = "";
os << "{";
for(auto i : coins) {
os << sep << i.second << " x " << i.first << 'c';
sep = ", ";
}
os << "}";
return os;
}
int test_change(long money, long price, const coin_bag& expected)
{
auto actual = getChange(money, price);
if (actual == expected) {
// passed
return 0;
}
// failed!
std::cout << "Failed: getChange(" << money << ", " << price << ")"
<< " == " << actual << " != " << expected << std::endl;
return 1;
}
int main()
{
return test_change(0, 0, {})
+ test_change(-1, 0, {})
+ test_change(0, 1, {}) // underpaid
+ test_change(0, -1, {{1, 1}}) // refund
+ test_change(9, 0, {{5, 1}, {1, 4}})
// and the examples from the original comments:
+ test_change(314, 199, {{100, 1}, {10, 1}, {5, 1}})
+ test_change(400, 314, {{50, 1}, {25, 1}, {10, 1}, {1, 1}})
+ test_change(45, 34, {{10, 1}, {1, 1}})
;
}
Enhancement: show coin names
#include <map>
#include <functional>
using coin_bag = std::map<unsigned int, unsigned long>;
static const std::map<unsigned int, const char*, std::greater<unsigned int>>
us_coins = {{100, "$1"}, {50, "50¢"}, {25, "25¢"}, {10, "10¢"}, {5, "5¢"}, {1, "1¢"}};
// Calculate the change from P-M as a bag of coins
// Empty result may mean M==P or an error condition such as underpayment.
// Otherwise, it's a map of coin value => number of coins
// Note: we make no attempt to avoid or detect integer overflow.
coin_bag getChange(long M, long P)
{
if (M <= P) {
// no change given
return {};
}
auto change = M - P;
coin_bag coins;
for (auto c: us_coins) {
auto q = change / c.first;
if (q > 0) {
coins[c.first] = q;
change -= c.first * q;
}
}
return coins;
}
// Test program
#include <iostream>
// helper
std::ostream& operator<<(std::ostream& os, const coin_bag& coins)
{
const char *sep = "";
os << "{";
for(auto i : coins) {
os << sep << i.second << " x " << us_coins.at(i.first);
sep = ", ";
}
os << "}";
return os;
}
int test_change(long money, long price, const coin_bag& expected)
{
auto actual = getChange(money, price);
if (actual == expected) {
// passed
return 0;
}
// failed!
std::cout << "Failed: getChange(" << money << ", " << price << ")"
<< " == " << actual << " != " << expected << std::endl;
return 1;
}
int main()
{
return test_change(0, 0, {})
+ test_change(-1, 0, {})
+ test_change(0, 1, {}) // underpaid
+ test_change(0, -1, {{1, 1}}) // refund
+ test_change(9, 0, {{5, 1}, {1, 4}})
// and the examples from the original comments:
+ test_change(314, 199, {{100, 1}, {10, 1}, {5, 1}})
+ test_change(400, 314, {{50, 1}, {25, 1}, {10, 1}, {1, 1}})
+ test_change(45, 34, {{10, 1}, {1, 1}})
;
}