CODEWITHSUNDEEP
c++c++14integer-overflow
Aradhye Agarwal
Aradhye Agarwal

Reputation: 449

Strange behaviour of integer overflow

I created the following code for finding the answer to the coin problem. This involves finding minimum number of coins of given k denominations (where each such coins are in infinite supply) to form a target sum n. In particular I have investigated the case where k=5, denominations = {2,3,4,5,6} and target sum n=100.

Code:

#include<iostream>
#include<algorithm>
using namespace std;

int coins[5] = {2,3,4,5,6};
int values[101];
int n=100;
int k=5;
int INF = INT_MAX;

int main()
{
    for (int x=1;x<=n;x++)
    {
        values[x] = INF;
        for (int j=1;j<=k;j++)
        {
            if (x-coins[j-1]>=0)
            {
                values[x] = min(values[x],values[x-coins[j-1]]+1);
            }
        }
    }
    cout<<values[100];

    return 0;
}

The output to this code that I received is -2147483632. Clearly some kind of overflow must be occurring so I decided to output INF+1. And I got INT_MIN as the answer. But I had also remembered that often while outputting some numbers beyond the int range there was no such problem.

I decided to output 1e11 and to my surprise the answer was still 1e11. Why is this happening, please help.

Upvotes: 0

Views: 94

Answers (2)

Damien
Damien

Reputation: 4864

Here:

 values[x] = min(values[x],values[x-coins[j-1]]+1);

For example, for x=3 and coins[0]=2, you add values[1] + 1.

However, values[1] = INT_MAX. Then, you get an undefined behavior when performing this calculation.

You can solve the issue with INF = INT_MAX - 1;

Upvotes: 1

eerorika
eerorika

Reputation: 238341

If your program performs arithmetic on signed integers that produces result that is outside the range of representable values - i.e. if such operation overflows - such as in the case of INT_MAX + 1 then the behaviour of the program is undefined.

I decided to output 1e11 and to my surprise the answer was still 1e11.

1e11 is a floating point literal. Floating point types have different range of representable values from int, and different requirements regarding overflow.

Upvotes: 0

Related Questions