How to get rid of the arithmetic overflow

Question

This is the code for the Triangle problem in codility that is throwing me an arithmetic overflow error.

int solution(vector<int> &A) {

    int i, n;
    n=A.size();
    sort(A.begin(), A.end());
    for(i=0; i<n-2; i++)
    {
        if((A[i]+A[i+1]>A[i+2])&&(A[i]+A[i+2]>A[i+1])&&(A[i+1]+A[i+2]>A[i]))
        {
            return 1;
        }
    }
    return 0;
}

It passes all the tests except for the 'extreme_arith_overflow1 overflow test, 3 MAXINTs' saying the code returns 0 but it expects 1. Anybody have any idea on how to fix this?

Answer 1

You store A.size() in n and then you loop until i<n and access A[i+2]. In the error cases this is A[A.size()] or even A[A.size()+1]. It's out of bounds. Fix the range of the loop.

The next problem occurs when the sum is larger than INT_MAX. Use the difference instead of the sum to avoid overflow. Remember that the elements are sorted with A[i] <= A[i+1] <= A[i+2]

int solution(vector<int> &A) {
    if (A.size() < 3) return 0;
    const auto n = A.size() - 2;
    std::sort(A.begin(), A.end());
    for(decltype(n) i = 0; i < n; ++i) {
        if((A[i]>A[i+2]-A[i+1])&&(A[i+2]>A[i+1]-A[i])&&A[i]>0) {
            return 1;
        }
    }
    return 0;
}