Vending machine change function

Question

Write a function that takes an amount of money M, a price P and returns the change given in the smallest number of coins. The following coins are available: 1c, 5c, 10c, 25c, 50c, and 1ドル. Time: 20min.

I'm looking for all sorts of reviews considering the time limit and environment.

Here's my code:

#include <iostream>
#include <vector>
std::vector<int> getChange(double M, double P)
{
 /*
 1c, 5c, 10c, 25c, 50c, and 1ドル
 getChange(3.14, 1.99) should return [0,1,1,0,0,1]
 getChange(4, 3.14) should return [1,0,1,1,1,0]
 getChange(0.45, 0.34) should return [1,0,1,0,0,0]
 */
 int denominations[] = {1, 5, 10, 25, 50, 100};
 std::vector<int> r(sizeof denominations / sizeof denominations[0]);
 // I had a floating-point problem here by computing cents = (M-P)*100;
 // it took me a few minutes to figure it out
 int cents = (int)(M*100) - (int)(P*100);
 for(int i = sizeof denominations / sizeof denominations[0] - 1; i >= 0; --i){
 r[i] = cents / denominations[i];
 cents = cents % denominations[i];
 }
 return r;
}
int main()
{
 auto change = getChange(5, 0.99);
 for(auto i : change){
 std::cout << i << ", ";
 }
 std::cout << std::endl;
 return 0;
}

Answer 1

You still have a floating point problem

If you change your line to this input:

auto change = getChange(0.04, 0.03);

you will get the following output:

2, 0, 0, 0, 0, 0,

As you can see, it answers with 2 pennies instead of one. The problem is with the line that you "fixed":

// I had a floating-point problem here by computing cents = (M-P)*100;
// it took me a few minutes to figure it out
int cents = (int)(M*100) - (int)(P*100);

You did notice a problem with your floating point conversion but you came to the conclusion that it was the subtraction that was the problem. The actual problem is that a floating point value of something like 0.03 can sometimes be slightly above or slightly below the actual value of 0.03. In this case, it is slightly below. When you convert this value to cents by using (int)(P*100), you end up converting something like 2.999999 to 2 instead of 3.

One way to avoid this problem is to round instead of truncate. So you can change your line to this to fix the problem:

int cents = (int) (100*(M-P) + 0.5);

• Douglas: I noticed it later, but that was the quick solution I found within the time limit to pass the test cases.
• Douglas: Why did you choose 0.5?
• JS1: Because when you do (int) (floatVar + 0.5) it rounds to the nearest integer value. Be careful, this only works for positive values. You could use the round() function if you are dealing with negative values as well.

Answer 2

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

• Douglas: The expected input was floating-point. I know it's not the correct way of handling money, but that's the task I was given.
• Toby Speight: In that case, pay attention to test cases involving binary/decimal rounding issues and non-finite numbers; you should also think about values where the precision is no longer within 0.01. Since the question didn't state, I had to assume you had a free choice of interface. The rest of the answer should still have some useful nuggets for you.

Answer 3

General approach looks good. But loop in the getChange I really do not like... So I have modified your code adding comments about every change I made. To make it easier to find - I have removed your comments - it is not indication that they not belong - just temporal workaround...

std::vector<int> getChange(double M, double P)
{
 //use vector instead of C-array
 //add const
 //reverse order of values
 const std::vector<int> denominations = {100,50,25,10,5,1};
 std::vector<int> r;//init empty vector - plan to use emplace_back
 //since the final size is known - 
 //set the proper capacity to avoid copying when resizing
 r.reserve(denominations.size());
 //use static_cast instead of C-style cast
 //adding rounding fix
 int cents = static_cast<int>(M*100+.5) - static_cast<int>(P*100+.5);
 for(auto val:denominations) { //get rid of horrible index loop
 //since we do not have index - use emplace_back
 r.emplace_back( cents / val); 
 cents %= val;
 }
 return r;
}

Now the function logic is the same - just the order of values in the result is opposite. I feel like code looks cleaner like this.

For the main - - it is just a preference - I would want to see count of coins with names. So I have extended the loop in main to add this functionality - but this modification is completely optional.

#include <iostream>
#include <vector>
#include <string>
int main()
{
 auto change = getChange(3.14, 1.99);
 //create parallel vector of names
 const std::vector<std::string> den_names = {"1$","50c","25c","10c","5c","1c"};
 //go over 2 vectors in parallel using const iterator
 auto it2 = den_names.cbegin();
 for(auto it = change.cbegin(); it != change.cend(); ++it,++it2) {
 if(*it > 0) {//skip zeros
 //show both - count of coins and coin name
 std::cout << *it << "*" << *it2 << ", "; 
 }
 }
 std::cout << std::endl;
 return 0;
}

• Douglas: Much more idiomatic, but it has the same floating-point problems as mine. Check @JS1's answer.

Answer 4

You can add simple check in your for loop for case less than 5.

if(cent < 5 ){ 
 returnChange[0] = cent; 
 break; 
}

• greybeard: Please argue the pros and cons of such a special case. (looks dangerous - what if there was a tuppence? Better check if smaller than smallest denomination larger than one cent.)