I'm working through algoexpert.io coding challenges and I'm having trouble undersatnding the suggested solution to one of the questions titled Non-Constructible Change
Here's the challenge question:
Given an array of positive integers representing the values of coins in your possession, write a function that returns the minimum amount of change (the minimum sum of money) that you cannot create. The given coins can have any positive integer value and aren't necessarily unique (i.e., you can have multiple coins of the same value).
For example, if you're given coins = [1, 2, 5], the minimum amount of change that you can't create is 4. If you're given no coins, the minimum amount of change that you can't create is 1.
// O(nlogn) time, O(n) size.
function nonConstructibleChange(coins) {
coins = coins.sort((a, b) => a - b); // O(nlogn) time operation
let change = 0;
for (coin of coins) {
if (coin > change + 1) return change + 1;
change += coin;
}
return change + 1;
}
My problem
I am not completely sure how did the author of the solution come up with the intuition that
if the current coin is greater than `change + 1`, the smallest impossible change is equal to `change + 1`.
I can see how it tracks, and indeed the algorithm passes all tests, but I'd like to know more about a process I could use to devise this rule.
Thank you for taking the time to read the question!
I managed to tackle it without the + 1 thing, by tracking the current minimum impossible change, like so:
function nonConstructibleChange(coins) {
let currentMinImpossibleChange = 1;
const sortedCoins = coins.sort((a,b) => a-b)
for(let i = 0; i < sortedCoins.length ; i += 1) {
if(currentMinImpossibleChange < sortedCoins[i]) return currentMinImpossibleChange
currentMinImpossibleChange += sortedCoins[i];
}
return currentMinImpossibleChange;
}
After a while thinking about that, I thought it was a probability problem. I mean, how many changes are possible given N coins?
This mean that I should combine every possibility. For example, given coins = [1, 5, 9], what's the minimum amount of change that can be made?
1 -> 1, 1+5, 1+9, 1+5+9.
5 -> 5, 5+9.
9 -> 9.
resulting in possible changes = [1, 6, 10, 15, 14, 9].
Then, the minimum amount of change that can be created using this 3 coins [1, 5, 9] should be 2.
By the way, if that was the case, this is a O(2^n) time because for every new coin (every new possibility) the number of calculations double.
Unfortunately, that is not the case...
When integers are sorted, we can always track the highest constructible value by doing a cumulative sum of the sorted integers.
For example, coins = [1, 2, 5] ==> 1,2,3,5,6,7
At any point, if the next integer is larger than max constructible + 1, then there is no way to construct max constructible + 1.
[1] mc=1 ---> 2
[1, 2] mc=3 ---> 4
[1, 2, 5] mc=7 ---> 8
If the current integer is greater than mc + 1, the smallest impossible change is equal to mc + 1.
So in this case, for [1, 2, 5] the smallest value is 4.
It can be done like this (i am using go)
func NonConstructibleChange(array []int) int {
sort.Ints(array)
ncc :=1
for i:=0; i< len(array) && array[i]<=ncc; i++{
ncc +=array[i]
}
return ncc
}
This one took me a while too, but this was how I made sense of it:
Assume you've proven you can make 1-8 cents.
You go to the next iteration and want to know if you can make 9 cents. So you iterate to the next new coin in the sorted list.
if newCoin < 9:
if newCoin == 9:
if newCoin > 9:
And that's where the change + 1 comes from. (your variable change = 8)
if the current coin is greater than `change + 1`, the smallest impossible change is equal to `change + 1`.