4
\$\begingroup\$

Make change like at a cash register

Input is the denominations of the currency and the sum
In test case only coins are entered

Return how many of each denomination
Return the fewest possible denomination count (don't return all pennies)

Check for style, efficiency, correctness, and anything else you want to check.

// test
for (int i = 1; i <= 200; i++)
{
    Dictionary<int, int> change = MakeChange(new List<int> { 1, 5, 10, 25, 50 }, i);
    Debug.WriteLine($"sum {i}");
    int sum = 0;
    foreach (KeyValuePair<int, int> coins in change)
    {
        sum += coins.Key * coins.Value;
        Debug.WriteLine($"  coin {coins.Key}  count {coins.Value} ");
    }
    if (i != sum)
    {
        Debug.WriteLine("problem");
    }
}
// end test

private static Dictionary<int, int> MakeChange(List<int> coins, int sum)
{
    if(sum < 0 || coins.Count == 0)
    {
        throw new ArgumentOutOfRangeException();
    }
    Dictionary<int, int> change = new Dictionary<int, int>();
    foreach (int coin in coins.Distinct().Where(x => x > 0).OrderByDescending(x => x))
    {               
        int j = sum / coin;  //integer math rounds down
        if (j > 0)
        {
            change.Add(coin, j);
        }
        sum -= j * coin;
        if (sum == 0)
            return change;
    }
    return null;
}
\$\endgroup\$
6
\$\begingroup\$

You have implemented the greedy algorithm for making change: starting with the largest denomination, divide, then use the smaller coins to handle the remainder.

That works for many coin systems, but in the general case, it fails to produce optimal results:

Greedy method

For the so-called canonical coin systems, like the one used in US and many other countries, a greedy algorithm of picking the largest denomination of coin which is not greater than the remaining amount to be made will produce the optimal result. This is not the case for arbitrary coin systems, though: if the coin denominations were 1, 3 and 4, then to make 6, the greedy algorithm would choose three coins (4,1,1) whereas the optimal solution is two coins (3,3).

Therefore, if you want to use as few coins as possible, where the set of denominations is arbitrarily picked by the user, you have to use a different algorithm — typically one based on .

So, either your code is wrong, or needs a comment to warn of that significant caveat.

\$\endgroup\$
  • \$\begingroup\$ Good catch. If you have a value > 1/2 the next then this could come into play. \$\endgroup\$ – paparazzo Jul 21 '17 at 21:23
  • \$\begingroup\$ I don't know how to handle this. If I just strike out that requirement then it invalidates your answer. To close it as not working code I think is kind of harsh. I will flag a mod. \$\endgroup\$ – paparazzo Jul 21 '17 at 21:29
  • 1
    \$\begingroup\$ You hadn't been aware of this issue when you posted the code for review. Now an answer has pointed it out to you. That's fine — identifying unexpected failures is one of the purposes of Code Review. \$\endgroup\$ – 200_success Jul 21 '17 at 21:39
  • \$\begingroup\$ I did not catch that you are a mod. \$\endgroup\$ – paparazzo Jul 21 '17 at 21:45
3
\$\begingroup\$

Just some notes about your code. This

if(sum < 0 || coins.Count == 0)
{
    throw new ArgumentOutOfRangeException();
}

is bad since you throw the same exception for different parameters and without any details. Also I believe ArgumentException suits much better for coins.Count == 0. And you doesn't check coins on null.

Also it would be better to have ability to pass any IEnumerable<int> as coins rather than List<int> only. The same can be applied to return type of the method: Dictionary<int, int> can be replaced with IEnumerable<Tuple<int, int>> which allows you to use yield return and yield break. Benefit of this approach is that returned collection will be immutable (of course you could use IReadOnlyDictionary, but I prefer IEnumerable in this case).

Thus I would rewrite the MakeChange method like this:

private static IEnumerable<Tuple<int, int>> MakeChange(IEnumerable<int> coins, int sum)
{
    if (coins == null)
        throw new ArgumentNullException(nameof(coins));

    if (!coins.Any())
        throw new ArgumentException("Empty coins collection.", nameof(coins));

    if (sum < 0)
        throw new ArgumentOutOfRangeException(nameof(sum), sum, "Sum is negative.");

    var orderedCoins = coins.Distinct().Where(x => x > 0).OrderByDescending(x => x);
    foreach (var coin in orderedCoins)
    {               
        int j = sum / coin;  //integer math rounds down
        if (j > 0)
            yield return Tuple.Create(coin, j);

        sum -= j * coin;
        if (sum == 0)
            yield break;
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.