Strange behaviour of integer overflow

  c++, c++14, 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.

Source: Windows Questions C++

LEAVE A COMMENT