The Coin Change Problem (Hard)
Good morning! Here's our prompt for today.
You may see this problem at Facebook, Amazon, Ebay, Tableau Software, Intercom, Reddit, Two Sigma, Twilio, Flatiron Health, Toast, Automation Anywhere, Sumo Logic, Blend, Bosch Global, Servicenow, Zynga, Riot Games, and Sony.
If I give you coins of denominations {3, 7, 9} (a coin worth 3 cents, a coin worth 7 cents, etc.), can you tell me the minimum number of coins that are needed to make a total of 37? You can assume that an infinite supply of all these coins are available to you.
This challenge is about solving the change making problem using dynamic programming. The task is to find the minimum number of coins that add up to a given denomination amount. We are given a set (via an array) of coins of different denominations and assume that each one of them has an infinite supply.
Examples
Here are a few examples of the given inputs and the expected output. Note, for all these examples other combinations are also possible. We are only interested in the minimum number of coins, regardless of the combination of coins.
11. coins = {2,3,5} amount = 11: use 3 coins, e.g., [3,3,5]
22. coins = {2,3,5,7} amount = 17: use 3 coins, e.g., [3,7,7]
33. coins = {2,3,7} amount = 15: use 4 coins, e.g., [2,3,3,7]
44. coins = {3,5} amount = 7: Not possible (inf)
55. coins = {2,3,5} amount = 1: Not possible (inf)For the combinations that are not possible, it is a convention to use infinity to represent such a solution.
Constraints
- Length of array
coins<=1000 - Each denomination will be a non zero positive integer
- Amount will be a non zero value and <=
1000 - Expected time complexity :
O(n^2) - Expected space complexity :
O(n)
xxxxxxxxxxvar assert = require('assert');function coinChange(coins, amount) { // Fill in this method return 1;}try { assert.equal(coinChange([2, 3, 5], 11), 3); console.log('PASSED: ' + 'First Test: coinChange([2, 3, 5], 11)');} catch (err) { console.log(err);}try { assert.equal(coinChange([2, 3, 5, 7], 17), 3); console.log('PASSED: ' + 'Second Test: coinChange([2, 3, 5, 7]');} catch (err) { console.log(err);}try { assert.equal(coinChange([2, 3, 7], 15), 4); console.log('PASSED: ' + 'Third Test: coinChange([2, 3, 7], 15)');