CODEWITHSUNDEEP
c++
firefly
firefly

Reputation: 201

Integer overflow issues

vector<int> getRow(int rowIndex) {
vector<int> result;
if(rowIndex < 0)   return result;
if(rowIndex == 0){
    result.push_back(1);
    return result;
}
for(int i = 0; i < rowIndex+1; i++){
    if(i == 0)  result.push_back(1);
    else{
        result.push_back(result[i-1] * (rowIndex+1-i)/i);
    }
}
return result;
}
int main()
{
    vector<int> tmp = getRow(30);
    for(int i = 0; i < tmp.size(); i++){
        cout << tmp[i] << " ";   
    }
    cout << endl;
    return 0;
}

This is the Pascal's triangle - coding problem from LeetCode, which asks to output the nth row of the Pascal triangle. With rowIndex=30, the output looks like:

1 30 435 4060 27405 142506 593775 2035800 5852925 14307150 30045015 54627300 86493225 119759850 145422675 -131213633 -123012780 -101304642 -73164463 -46209134 -25415023 -12102391 -4950978 -1722079 -502273 -120545 -23181 -3434 -367 -25 0

Obviously, there is an overflow problem. Now to fix this, I modified the line result.push_back(result[i-1] * (rowIndex+1-i)/i); to result.push_back((double)result[i-1] * (double)(rowIndex+1-i)/i);. And it produces the correct output: 

1 30 435 4060 27405 142506 593775 2035800 5852925 14307150 30045015 54627300 86493225 119759850 145422675 155117520 145422675 119759850 86493225 54627300 30045015 14307150 5852925 2035800 593775 142506 27405 4060 435 30 1

Can someone explain what exactly is the problem here? We know that the range of signed integer value is -2147483648 to 2147483647. Without casting, why at value 155117520 is printed as overflow -131213633?

Upvotes: 0

Views: 102

Answers (1)

AlexD
AlexD

Reputation: 32616

I the expression

result[i-1] * (rowIndex+1-i)/i

multiplication takes place first, and results in overflow:

result[i-1] * (rowIndex + 1-i)

and then the result gets divided by i, producing the negative output.

BTW, if you decide to cast, avoid casting to double due to possible rounding issues. You could try long instead, but it is perhaps better to use at the first place

vector<long>

or even

vector<unsigned long>

or, thanks to @WorldSEnder,

vector<unsigned long long>

Still, be aware that the standard does not guarantee that long or long long is longer than int. Neither it guarantees that int is in the range [-2147483648, 2147483647].

Upvotes: 3

Related Questions