Coin Determiner
Have the function CoinDeterminer(num) take the input, which will be an integer ranging from 1 to 250, and return an integer output that will specify the least number of coins, that when added, equal the input integer. Coins are based on a system as follows: there are coins representing the integers 1, 5, 7, 9, and 11. So for example: if num is 16, then the output should be 2 because you can achieve the number 16 with the coins 9 and 7. If num is 25, then the output should be 3 because you can achieve 25 with either 11, 9, and 5 coins or with 9, 9, and 7 coins.
I can solve it by recursion as follows:
int coinDeterminer(int num) {
final List<Integer> coins = List.of(1, 5, 7, 9, 11);
return coinDeterminer(coins, coins.size(), new ArrayList<>(), num);
}
int coinDeterminer(List<Integer> coins, int offset, List<Integer> subset, int num) {
if (num == 0) return subset.size();
if (num < 0) return Integer.MAX_VALUE;
if (offset == 0) return Integer.MAX_VALUE;
int count1 = coinDeterminer(coins, offset - 1, subset, num);
int coin = coins.get(offset - 1);
subset.add(coin);
num -= coin;
int count2 = coinDeterminer(coins, offset, subset, num);
subset.remove(subset.size() - 1);
return Math.min(count1, count2);
}
How does this mathematical solution reach the same solution?
int coinDeterminer(int num) {
if (num < 1 || num > 250) return -1;
if (num < 5) return num;
int count = num / 11;
int remainder = num % 11;
if (remainder == 0) return count;
else if (remainder % 2 == 1) return count + 1;
else return count + 2;
}
The solution tries a greedy approach first: an amount of $11n$ can be achieved by $n$ coins of value $11$ and this is clearly optimal.
For an amount of $11n+k$ with $0\le k<11$, we might be lucky and can take $n$ coins of value $11$ and one coin of value $k$. If $k$ is a valid denomination, this is clearly optimal (though alternative combinations might exist, but they cannot use fewer coins). This works when $k=1,5,7,9$, i.e., for all odd $k$ except $k=3$ because there are no 3-coins. However, when $k=3$, we can replace one of our $n$ 11-coins with a 9-coint and then use a 5-coin instead of that 3-coin and are done -- provided $n\ge 1$.
If $k$ is even (and non-zero), it is impossible to solve the problem with $n$ coins (cannot obtain more than $11n$ with them), nor with $n+1$ coins (for parity reasons), hence we will need at least $n+2$ coins. But as 1-coins are allowed, this can readily be done by taking $1$ 1-coin and the solution for $11n+(k-1)$ with $n+1$ coins.
We need to be careful when $n=0$: If $n=0$ and $k=3$, we cannot replace one 11-coin with a 9-coin as described above, hence we do need $3$ 1-coins. Likewise, if $n=0$ and $k=4$, the method in the third paragraph would lead us to a 1-coin plus the solution for $n00$ and $k=3$, so $4$ coins instead of $n+2$ coins.
This could explain all code of the second function (except the one returning $-1$ -- which can be removed as it applies only to undefined cases and so undefined behaviour is acceptable)