Created
September 23, 2025 11:51
-
-
Save antonvasin/24768ac3d0b2af9e660634e40f456f60 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* | |
| * # The problem | |
| Given a number `x` and a sorted array of coins `coinset`, write a function | |
| that finds a combination of these coins that add up to X | |
| There are an infinite number of each coin. | |
| This is hopefully familiar to making change for a given amount of money in a currency, but it gets more interesting if we remove the 1 coin and have “wrong” coins in the coinset. | |
| Return a map (or dictionary or whatever it is called in your preferred programming language such that each key is the coin, and each value is the number of times you need that coin. | |
| You need to only return a single solution, but for bonus points, return the one with the fewest number of coins. | |
| Don’t worry about performance or scalability for this problem. | |
| # A Specific example | |
| If x=7 and the coinset= [1,5,10,25], then the following are both solutions: | |
| `{1: 7}` since 7*1 = 7 | |
| `{1: 2, 5: 1}` since 1*2 + 5*1=7 | |
| # Some test cases for you to verify your approach works | |
| A. x = 6 coinset = [1,5,10,25] | |
| B. x = 6, coinset = [3,4] | |
| C. x = 6, coinset = [1,3,4] | |
| D. x = 6, coinset = [5,7] | |
| E. x = 16, coinset = [5,7,9] | |
| */ | |
| const sum = (res) => Object.entries(res).reduce((acc, [k, v]) => (acc += k * v), 0); | |
| function makeChange(x, coinSet) { | |
| let res = {}; | |
| for (const coin of coinSet) { | |
| if (x % coin === 0) return { [coin]: x / coin }; | |
| res[coin] ??= 0; | |
| res[coin] += 1; | |
| const sumRes = sum(res); | |
| if (sumRes === x) return res; | |
| } | |
| if (sum(res) !== x && coinSet.length) { | |
| coinSet.shift(); | |
| return makeChange(x, coinSet); | |
| } | |
| return res; | |
| } | |
| console.log(makeChange(6, [1, 5, 10, 25])); | |
| console.log(makeChange(6, [3, 4])); | |
| console.log(makeChange(6, [1, 3, 4])); | |
| console.log(makeChange(6, [5, 7])); | |
| console.log(makeChange(16, [5, 7, 9])); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment