Runtime error: addition of unsigned offset in leetcode

Question

I was solving a question on Leetcode(322. Coin Change) and I wrote my solution which is working on VScode. the code is:

int coinChange(vector<int>& coins, int amount) {
   int n = coins.size();
   vector<vector<int>> dp(n+1,vector<int>(amount+1,999));

   for(int i=0;i<n+1;i++)
      dp[i][0] = 0;
   for(int i=0;i<amount+1;i++){ 
      dp[0][i] = 999;
   }

   for(int i=1;i<n+1;i++){
      for(int j=1;j<amount+1;j++){
            if(coins[i-1]<=amount)
               dp[i][j] = min( dp[i][j-coins[i-1]]+1, dp[i-1][j] );
            else
               dp[i][j] = dp[i-1][j];
      }
   }

   if(dp[n][amount]>=999) return -1;
   return dp[n][amount];
}

upon running for testcase coins = [1,2,5], amount = 11, it I'm getting the following error

Line 1117: Char 34: runtime error: addition of unsigned offset to 0x504000000110 overflowed to 0x50400000010c (stl_vector.h)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/13/../../../../include/c++/13/bits/stl_vector.h:1126:34

Start by creating a proper minimal reproducible example, with the failing input hard-coded into the main function, that you can build, run and debug locally on your own system. Then install MinGW and use it with its undefined-behavior sanitizer, to try and replicate the error you're getting. — Some programmer dude
– Some programmer dude, Commented Jul 25, 2024 at 13:53

OfNothing · Accepted Answer · 2024-07-25 14:01:25Z

1

In the line:

dp[i][j] = min( dp[i][j-coins[i-1]]+1, dp[i-1][j] );

When indexing into dp, j-coins[i-1] can be less than 0 because coins[i-1] can be grater than j.

This could cause the runtime error you are seeing. I would suggest running the code under a debugger and stepping through the loop to see what the values of the indexes are at different points in time.

answered Jul 25, 2024 at 14:01

OfNothing

6353 silver badges14 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Ankur Yadav Over a year ago

Yeah, I was checking the wrong cond. : if(coins[i-1]<=amount) it should be : if(coins[i-1]<=j).

Collectives™ on Stack Overflow

Runtime error: addition of unsigned offset in leetcode

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related