0

I am trying to solve Leetcode Problem 322. Here's the description quoted from the site.

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

I have written 2 recursive solutions, 1 in Python and 1 in Javascript. For some reason, the one in Javascript doesn’t produce the correct values for the same input, while the Python one always do.

Would like to ask if anyone knows what could be the reason for the difference in output. I tried with the following test cases:

coins = [1,2,5], amount = 11 => Expected: 3 
coins = [1,2], amount = 2 => Expected: 1

Here's the code I've written in the respective languages.

Javascript

var coinChange = function(coins, amount) {
    coins = coins.sort((a,b) => b -a )
    ans = helper(coins, amount, 0)
    if (ans >= Number.MAX_VALUE) {
        return -1
    }
    return ans;
};


function helper(coins, amount, pos) {
    if (pos >= coins.length || amount < 0) {
        return Number.MAX_VALUE; 
    } else if (amount === 0) {
        return 0; 
    }

    left = helper(coins, amount - coins[pos], pos) + 1
    right = helper(coins, amount, pos + 1)

    return Math.min(left, right)
}

Using the above 2 test cases, it gets both test cases wrong.

coins = [1,2,5], amount = 11 => Expected: 3, gets 2
coins = [1,2], amount = 2 => Expected: 1, gets 2

Python

def coinChange(coins, amount):
    coins = sorted(coins, reverse = True)    
    ans = helper(coins, amount, 0)
    if (ans >= float("inf")):
        return -1
    return ans

def helper(coins, amount, pos):
    if (pos >= len(coins) or amount < 0):
        return float("inf")
    elif (amount == 0):
        return 0
    left = helper(coins, amount - coins[pos], pos) + 1
    right = helper(coins, amount, pos + 1)

    return min(left, right)

Using the above 2 test cases, it gets both tests correct.

coins = [1,2,5], amount = 11 => Expected: 3, gets 3
coins = [1,2], amount = 2 => Expected: 1, gets 1
T.J. Crowder
  • 1,031,962
  • 187
  • 1,923
  • 1,875
Prashin Jeevaganth
  • 1,223
  • 1
  • 18
  • 42
  • Have you tried debugging your code? [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173) and [How to debug small programs](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) – VLAZ Dec 09 '21 at 15:25
  • Yes, I have done some debugging before posting this question, using `print` debugging. Would think that there was a problem with the recursion tree in the javascript code, but couldn't verify what could be the cause. Surprisingly the Python equivalent worked, so wanted to check here if the error in the Javascript code could be due to something Javascript specific – Prashin Jeevaganth Dec 09 '21 at 15:28
  • 2
    The problem is that you've not declared your variables. All of them are implicit globals. Therefore all the recursive executions use the same data and mix it up. – VLAZ Dec 09 '21 at 15:30
  • @VLAZ Thanks for the big tip, didn't manage to notice this during my initial attempts at debugging – Prashin Jeevaganth Dec 09 '21 at 15:37

1 Answers1

0

The Javascript code gets the expected answer by adding let to the return values to each of the recursive calls.

For example, left = helper(coins, amount - coins[pos], pos) + 1 is changed to

let left = helper(coins, amount - coins[pos], pos) + 1

Prashin Jeevaganth
  • 1,223
  • 1
  • 18
  • 42