• 1

• 87.2k
• 14
• 104
• 322

• 87.2k
• 14
• 104
• 322

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}})
 ;
}