Incorrect Test Case - 518. Coin Change II

[Mehul10]

LeetCode Username

mehhul

Problem Number, Title, and Link

518. Coin Change II https://leetcode.com/problems/coin-change-ii/description/

Bug Category

Incorrect test case (Output of test case is incorrect as per the problem statement)

Bug Description

The problem statement states "The answer is guaranteed to fit into a signed 32-bit integer."
However the answer overflows for a test case on running the code.

Language Used for Code

C++

Code used for Submit/Run operation

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n=coins.size();
        vector<int> dp(amount+1,0);
        dp[0]=1;
        for(int i=0;i<n;i++)
        {
            for(int j=1;j<=amount;j++)
            {
                if(j>=coins[i])
                {
                    dp[j]+=dp[j-coins[i]];
                }
            }
        }
        return dp[amount];        
    }
};

Expected behavior

This code overflows the integer value on this line dp[j]+=dp[j-coins[i]];.
Here the test case on which this happens

amount = 4681
coins = [2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44,46,48,50,52,54,56,58,60,62,64,66,68,70,72,74,76,78,80,82,84,86,88,90,92,94,96,98,100,102,104,106,108,110,112,114,116,118,120,122,124,126,128,130,132,134,136,138,140,142,144,146,148,150,152,154,156,158,160,162,164,166,168,170,172,174,176,178,180,182,184,186,188,190,192,194,196,198,200,202,204,206,208,210,212,214,216,218,220,222,224,226,228,230,232,234,236,238,240,242,244,246,248,250,252,254,256,258,260,262,264,266,268,270,272,274,276,278,280,282,284,286,288,290,292,294,296,298,300,302,304,306,308,310,312,314,316,318,320,322,324,326,328,330,332,334,336,338,340,342,344,346,348,350,352,354,356,358,360,362,364,366,368,370,372,374,376,378,380,382,384,386,388,390,392,394,396,398,400,402,404,406,408,410,412,414,416,418,420,422,424,426,428,430,432,434,436,438,440,442,444,446,448,450,452,454,456,458,460,462,464,466,468,470,472,474,476,478,480,482,484,486,488,490,492,494,496,498,500,502,504,506,508,510,512,514,516,518,520,522,524,526,528,530,532,534,536,538,540,542,544,546,548,550,552,554,556,558,560,562,564,566,568,570,572,574,576,578,580,582,584,586,588,780,936,1170,1560,2340,4680]

Screenshots

Additional context

[wktang]

oj-leetcode commented: Hello,

Your reported issue has been relayed to our team for thorough investigation. We appreciate your patience as we work to address and resolve this matter. We will reach out to you when we have updates regarding the issue.

If you have any further questions or concerns in the meantime, please feel free to let us know.

Best regards,
LeetCode Support Team

[stormsunshine]

I think one more constraint should be added that all intermediate results will fit in signed 32-bit integers as well.

After adding this constraint, all the existing test cases should be checked and the test cases that do not meet the constraint should be removed.

[wktang]

Epiphania_Ekenimoh commented: Hi there,

Thank you for taking the time to share your feedback with us.

After careful consideration, we have decided not to move forward with the changes suggested in your feedback.

Please know that your input is important to us. Your continued feedback is greatly appreciated as we work towards improving our platform.

Best regards,
LeetCode Support Team

[Mehul10]

Hi, could you please provide the reason for not moving forward with this? As I see this is a very classic problem which many first time learners use to understand the concepts of Dynamic Programming(DP), while in this test case final answer is within the 32 bit limit, but the intermediate answers overshoot and they don't even fit within long long (they fit only in an unsigned long long) which would be really tricky/confusing for people who are first time solvers and are here to understand the concepts.