CODEWITHSUNDEEP
pythonalgorithmdynamic-programming
M00000001
M00000001

Reputation: 309

Cannot Figure Why My Code Does not Work for A Particular Case(Coin Change from Leetcode)

Here is the link for the question:https://leetcode.com/problems/coin-change/

Question:

You are given coins of different denominations and a total amount of money amount. Write a function to compute 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.

Example 1:

Input: coins = [1, 2, 5], amount = 11

Output: 3

Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3

Output: -1

I came up with the following code, it passed the test case in Example 1 above, but didn't pass the test case from Example 2

Here is my code by the following the algorithm described by the solution(screenshot attached)

ScreenshotPartI

ScreenshotPartII

The following code return 0 while I expect returning -1 since result equals with sys.maxsize

import sys
#declare global look up dictionary to store key (amount) and value (minimum number of coins)
lookup_dict = {}
#declare minimum number of coins and use the maximum number in python as place holder
minimum = sys.maxsize
def coinChange(coins,amount):
    result = coinChangeAux(coins, amount)
    return -1 if result==sys.maxsize else result

def coinChangeAux(coins, amount):
    #since we will modify minimum and lookup_dict, we put "global" in front of them
    global minimum,lookup_dict
    if amount in lookup_dict.keys():
        return lookup_dict[amount]
    if amount <= 0:
        lookup_dict[amount]=0
        return lookup_dict[amount]
    if not coins:
        return -1 
    for i in coins:
        if amount>=i:
            minimum = min(minimum,coinChange(coins,amount-i)+1)  
    lookup_dict[amount] = minimum
    return lookup_dict[amount]
coins=[2]
amount = 3
coinChange(coins,amount)

I tried to debug the above code by returning result only in coinChange function below and result indeed returns 9223372036854775807 that is equal to sys.maxsize (so I expect the above coinChange function should return -1 since result equals with maxsize

import sys
#declare global look up dictionary to store key (amount) and value (minimum number of coins)
lookup_dict = {}
#declare minimum number of coins and use the maximum number in python as place holder
minimum = sys.maxsize
def coinChange(coins,amount):
    result = coinChangeAux(coins, amount)
    return result

def coinChangeAux(coins, amount):
    #since we will modify minimum and lookup_dict, we put "global" in front of them
    global minimum,lookup_dict
    if amount in lookup_dict.keys():
        return lookup_dict[amount]
    if amount <= 0:
        lookup_dict[amount]=0
        return lookup_dict[amount]
    if not coins:
        return -1 
    for i in coins:
        if amount>=i:
            minimum = min(minimum,coinChange(coins,amount-i)+1)  
    lookup_dict[amount] = minimum
    return lookup_dict[amount]
coins=[2]
amount = 3
coinChange(coins,amount)

Upvotes: 1

Views: 111

Answers (1)

M Oehm
M Oehm

Reputation: 29116

When you recurse, you call coinChange, which turns sys.maxsize into −1. So the new value for minimum will be −1 + 1 = 0. (And it's a good thing that sys.maxsize + 1 doesn't overflow in Python.)

Call the wrapper function coinChange only once and call coinChangeAux recursively:

for i in coins:
    if amount >= i:
        minimum = min(minimum, coinChangeAux(coins, amount - i) + 1)

Upvotes: 1

Related Questions