1

I am working on this problem on Leetcode 322 Coin Change.

The question is; 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

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

return 3 (11 = 5 + 5 + 1)

Example 2

coins = [2], amount = 3

return -1

The following is JAVA DP Solution;

public int coinChange(int[] coins, int amount) {
    
if(amount==0) return 0;

int[] dp = new int[amount+1];
dp[0]=0; // do not need any coin to get 0 amount
for(int i=1;i<=amount; i++)
    dp[i]= Integer.MAX_VALUE;

for(int i=0; i<=amount; i++){
    for(int coin: coins){
        if(i+coin <=amount){
            if(dp[i]!=Integer.MAX_VALUE){
                if(dp[i+coin] >= dp[i] + 1)
                    dp[i+coin] = dp[i] + 1;
            }
        }
    }
}

if(dp[amount] >= Integer.MAX_VALUE)
    return -1;

return dp[amount];
}

When I run the test case with coins = [1,2147483646], amount = 2 I always get the error message

java.lang.ArrayIndexOutOfBoundsException: -2147483648 for line

if(dp[i+coin] >= dp[i] + 1)

I am trying to understand why it would happen. I am thinking the coin value 2147483646 won't pass this line if(i+coin <=amount) to affect the following code. right?

SOLVED! By change if(i+coin <=amount) to if(i+coin <=amount && i + coin >=0))

Community
  • 1
  • 1
zhuangr
  • 51
  • 6
  • [How does Java handle integer underflows and overflows and how would you check for it?](http://stackoverflow.com/q/3001836/669576). – 001 Oct 28 '16 at 02:54
  • Why are you using the array of that big size `long[] dp = new long [amount+1];` You are passing amount to initialize the array which is `2147483647` is it really needed? Overflow occurs in your code. – thetraveller Oct 28 '16 at 02:54

0 Answers0