 # artemkorsakov's solution

## to Change in the C# Track

Published at Jun 27 2019 · 0 comments
Instructions
Test suite
Solution

Correctly determine the fewest number of coins to be given to a customer such that the sum of the coins' value would equal the correct amount of change.

## For example

• An input of 15 with [1, 5, 10, 25, 100] should return one nickel (5) and one dime (10) or [5, 10]
• An input of 40 with [1, 5, 10, 25, 100] should return one nickel (5) and one dime (10) and one quarter (25) or [5, 10, 25]

## Edge cases

• Does your algorithm work for any given set of coins?
• Can you ask for negative change?
• Can you ask for a change value smaller than the smallest coin value?

## Running the tests

To run the tests, run the command `dotnet test` from within the exercise directory.

Initially, only the first test will be enabled. This is to encourage you to solve the exercise one step at a time. Once you get the first test passing, remove the `Skip` property from the next test and work on getting that test passing. Once none of the tests are skipped and they are all passing, you can submit your solution using `exercism submit Change.cs`

## Further information

For more detailed information about the C# track, including how to get help if you're having trouble, please visit the exercism.io C# language page.

## Source

Software Craftsmanship - Coin Change Kata https://web.archive.org/web/20130115115225/http://craftsmanship.sv.cmu.edu:80/exercises/coin-change-kata

### ChangeTest.cs

``````// This file was auto-generated based on version 1.3.0 of the canonical data.

using System;
using Xunit;

public class ChangeTest
{
[Fact]
public void Single_coin_change()
{
var coins = new[] { 1, 5, 10, 25, 100 };
var target = 25;
var expected = new[] { 25 };
Assert.Equal(expected, Change.FindFewestCoins(coins, target));
}

[Fact(Skip = "Remove to run test")]
public void Multiple_coin_change()
{
var coins = new[] { 1, 5, 10, 25, 100 };
var target = 15;
var expected = new[] { 5, 10 };
Assert.Equal(expected, Change.FindFewestCoins(coins, target));
}

[Fact(Skip = "Remove to run test")]
public void Change_with_lilliputian_coins()
{
var coins = new[] { 1, 4, 15, 20, 50 };
var target = 23;
var expected = new[] { 4, 4, 15 };
Assert.Equal(expected, Change.FindFewestCoins(coins, target));
}

[Fact(Skip = "Remove to run test")]
public void Change_with_lower_elbonia_coins()
{
var coins = new[] { 1, 5, 10, 21, 25 };
var target = 63;
var expected = new[] { 21, 21, 21 };
Assert.Equal(expected, Change.FindFewestCoins(coins, target));
}

[Fact(Skip = "Remove to run test")]
public void Large_target_values()
{
var coins = new[] { 1, 2, 5, 10, 20, 50, 100 };
var target = 999;
var expected = new[] { 2, 2, 5, 20, 20, 50, 100, 100, 100, 100, 100, 100, 100, 100, 100 };
Assert.Equal(expected, Change.FindFewestCoins(coins, target));
}

[Fact(Skip = "Remove to run test")]
public void Possible_change_without_unit_coins_available()
{
var coins = new[] { 2, 5, 10, 20, 50 };
var target = 21;
var expected = new[] { 2, 2, 2, 5, 10 };
Assert.Equal(expected, Change.FindFewestCoins(coins, target));
}

[Fact(Skip = "Remove to run test")]
public void Another_possible_change_without_unit_coins_available()
{
var coins = new[] { 4, 5 };
var target = 27;
var expected = new[] { 4, 4, 4, 5, 5, 5 };
Assert.Equal(expected, Change.FindFewestCoins(coins, target));
}

[Fact(Skip = "Remove to run test")]
public void No_coins_make_0_change()
{
var coins = new[] { 1, 5, 10, 21, 25 };
var target = 0;
Assert.Empty(Change.FindFewestCoins(coins, target));
}

[Fact(Skip = "Remove to run test")]
public void Error_testing_for_change_smaller_than_the_smallest_of_coins()
{
var coins = new[] { 5, 10 };
var target = 3;
Assert.Throws<ArgumentException>(() => Change.FindFewestCoins(coins, target));
}

[Fact(Skip = "Remove to run test")]
{
var coins = new[] { 5, 10 };
var target = 94;
Assert.Throws<ArgumentException>(() => Change.FindFewestCoins(coins, target));
}

[Fact(Skip = "Remove to run test")]
public void Cannot_find_negative_change_values()
{
var coins = new[] { 1, 2, 5 };
var target = -5;
Assert.Throws<ArgumentException>(() => Change.FindFewestCoins(coins, target));
}
}``````
``````﻿using System;
using System.Collections.Generic;
using System.Linq;

public static class Change
{
public static int[] FindFewestCoins(int[] coins, int target)
{
if (target < 0)
{
throw new ArgumentException("Negative change values");
}

if (target == 0)
{
return new int[] { };
}

if (coins.Contains(target))
{
return new int[] { target };
}

var validCoins = GetValidCoins(coins, target);

var counts = new int[validCoins.Length];
if (target % validCoins[validCoins.Length - 1] == 0)
{
counts[counts.Length - 1] = target / validCoins[validCoins.Length - 1];
return GetResult(validCoins, counts);
}

if (validCoins.Length == 1)
{
throw new ArgumentException("No combination can add up to target");
}

counts = GetMinimalCounts(validCoins, target);
return GetResult(validCoins, counts);
}

private static int[] GetValidCoins(int[] coins, int target)
{
var result = coins.Where(coin => 0 < coin && coin < target).OrderBy(coin => coin).ToArray();
if (result.Length == 0)
{
throw new ArgumentException("No combination can add up to target");
}

return result;
}

private static int[] GetResult(int[] coins, int[] counts)
{
var result = new List<int>();
for (var i = 0; i < counts.Length; i++)
{
for (var j = 0; j < counts[i]; j++)
{
}
}

return result.ToArray();
}

private static int[] GetMinimalCounts(int[] coins, int target)
{
for (var candidate = target / coins[coins.Length - 1] + 1; candidate <= target / coins; candidate++)
{
var tempCounts = GetCandidateCounts(coins, target, candidate);
if (tempCounts != null)
{
return tempCounts;
}
}

throw new ArgumentException("No combination can add up to target");
}

private static int[] GetCandidateCounts(int[] coins, int target, int candidate)
{
if (candidate == 0 || coins.Length == 0)
{
return null;
}

for (int i = candidate; i >= 0; i--)
{
var tempCounts = new int[coins.Length];
tempCounts[tempCounts.Length - 1] = i;
var tempTarget = target - coins[coins.Length - 1] * tempCounts[tempCounts.Length - 1];
if (tempTarget == 0)
{
return tempCounts;
}
else if (tempTarget > 0)
{
var tempCoins = new int[coins.Length - 1];
Array.ConstrainedCopy(coins, 0, tempCoins, 0, coins.Length - 1);
var newTempCounts = GetCandidateCounts(tempCoins, tempTarget, candidate - i);
if (newTempCounts != null)
{
Array.ConstrainedCopy(newTempCounts, 0, tempCounts, 0, newTempCounts.Length);
return tempCounts;
}
}
}

return null;
}
}``````