Project Euler - Problem 31: Coin sums

JavaScript
1

Tell us what’s happening:
Ok, I am stuck on the stage ‘what should I google for this one’.
My first idea is just generate power set of all these coins, but I don’t even wanna go there, because it’s exponential complexity stuff.

I feel like I am missing some basic algorithm knowledge to come up with decent approach. So the hints in terms of where to start research are appreciated.

  **Your code so far**

function coinSums(n) {
  const coins = [1, 2, 5, 10, 20, 50, 100, 200];
  return n;
}

coinSums(200);

  **Your browser information:**

User Agent is: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/104.0.0.0 Safari/537.36

Challenge: Project Euler - Problem 31: Coin sums

Link to the challenge:

3

Yes, I definitely see how memoization can be used here, so great thanks for that direction.

I’ve run into another issue: even when I wrote manually test cases for all possible n from 1 to 10, I still wasn’t able to come up with patterns which would allow me to build the algorithm.

But now I found out that this challenge is about some typical combinatorics problem, so I am diving into some math right now.

4

I moved further and have some code.

Now the problem I am facing is this:

for n===3
expected behaviour is returning 2
because combos for this case are:

  • 111, 21

However, my solution is returning 3, because it is considering 21 and 12 two different combos and spitting amount of combos for

  • 111, 21, 12

If I will start building some arrays or strings dynamically I can sort them and remove duplicates. But I am afraid this will increase complexity too much. One way to find out tho.

The code for now:

function coinSums(n, memo = {}) {
  // console.log(n, memo); //>>> testing purposes only
  //  memoizing
  if (n in memo) {return memo[n];}
  const coins = [1, 2, 5, 10, 20, 50, 100, 200];
  // base cases
  if (n === 0) {return 1;}
  // if (n < 0) {return 0;} //>>> not needed it's better to quit the loop early than increase stack with this
  // recursive step
  let combos = 0;
  for (let coin of coins) {
    if (coin > n) {break;} // for n === 8 steps for coins 10 and higher not needed
    combos += coinSums(n - coin, memo);
  }
  memo[n] = combos
  return memo[n];
}

for (let i = 1; i <=10; i++) {
  console.log('CASE ', i);
  console.log('RESULT ', coinSums(i));
  console.log('--------------');
}
5

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.