[Code Challenge] Coin Change

Cover Image for [Code Challenge] Coin Change
Antonio Maldonado
Antonio Maldonado

The problem states that we are gonna have 2 parameters, being the first one an array of integers and the second one a target amount.

So, if we analyze the problem, we have no limitations on how many times we can use the same coin. that's our first hint; and the second one is that, in the given case that we don't get a match, we can return an empty array, if our target is an amount of 5 and we hace just 2 coins, one with value of 3 and the other one with a value of 4 it's not possible to get that amount.

Here we have a solution using JavaScript. The explanation is the following one:

Let's imagine that we are using an array like this: [5, 10, 2, 1], and our target value is 17.

first we sort the array in descending order using the sort method in the given array. In other words now our current array is [10, 5, 2, 1]

Then we use the array method "reduce", this method returns an empty by default, in the given case we don't find a match, so we expect an empty array.

The prototype method receives 2 parameters, the first one is an array that is gonna be iterated, an accumulator, and the second one the current value, in the first iteration our accumulator array is empty, and the first number we are using is the one with the minimum value.

Then we proceed with a division, we calculate how many times we can use this "coin". So, in this iteration we are calculating how many times we can use the coin $10. We are going to find that 17/10 = 1, then we are going to use the method "concat". This method can let us fulfill an array with the same element several times, we are indicating that we are going to fulfill our accumulator array with 1 times the coin $10.

At the end we calculate how much is left, knowing that we already have used the coin $10 the times we needed it, we use that times in order to know how much is remaining using the module operator.

We repeat this same process until we run over the whole array.

function coinChange(coins, amount) {
    coins.sort((a, b) => b - a); //Sort array in descending order

    //auxArray => initial value or the previously returned value
    //coin => the value of the current element of the iteration
    const result = coins.reduce((auxArray, coin) => { //Not suitable for empty arrays!
        let count = Math.floor(amount/coin); //Round number, number of times a certain coin fits
        auxArray = auxArray.concat(Array(count).fill(coin)); //Add the number of times the coin fits into the auxiliar array
        amount %= coin; //calculate the remaining amount
        
        return auxArray;
    }, []); //Returns an empty array by default

    // Return the result array
    console.log(result);
    return result;
}

coinChange([5, 2, 10, 1], 17); //[10, 5, 2]
coinChange([8, 1, 9, 4], 13); //[9, 4]
coinChange([10, 1, 5, 2], 0);//[] => no match, returns an empty array
coinChange([1, 3, 4, 5, 6], 2);//[1,1]
coinChange([1, 6, 7, 10, 11], 35);//[11, 11, 11, 1, 1]

I provided you with different test scenarios, in order to validate that the algorithm worked. I also share you the python code.

import functools

def coinChange(coins, amount):
    coins.sort(reverse=True)

    result = []
    count = 0

    for coin in coins:
        count = int(amount/coin)
        result = result + [coin]*count
        amount %= coin
        
    print(result)    
    return result

if __name__ == '__main__':
    coinChange([5, 2, 10, 1], 17); #[10, 5, 2]
    coinChange([8, 1, 9, 4], 13); #[9, 4]
    coinChange([10, 1, 5, 2], 0); #[] => no match, returns an empty array
    coinChange([1, 3, 4, 5, 6], 2); #[1,1]
    coinChange([1, 6, 7, 10, 11], 35); #[11, 11, 11, 1, 1]