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?

First of all make sure that you don't go out of bounds of your vector. (which you will do with the code you currently show) Secondly perhaps use unsigned int instead, (if no value can be negative) or maybe long long (or unsigned long long) for a 64-bit type? Also, you should probaby be doing some input validation to make sure the input you read is valid to begin with. — Some programmer dude
– Some programmer dude, Commented Jun 3, 2020 at 9:37
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. — Thomas Sablik
– Thomas Sablik, Commented Jun 3, 2020 at 9:43
@Someprogrammerdude yesss thanks i fixed the out of bounds issue and validated input :) — monkikat
– monkikat, Commented Jun 3, 2020 at 12:43

Thomas Sablik · Accepted Answer · 2020-06-03 13:27:07Z

0

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;
}

edited Jun 3, 2020 at 13:27

answered Jun 3, 2020 at 9:45

Thomas Sablik

16.5k7 gold badges38 silver badges69 bronze badges

Sign up to request clarification or add additional context in comments.

10 Comments

monkikat Over a year ago

Hey thanks for your answer! Fixed the out of bounds issue but i still seem to be getting an arithmetic overflow error.

jvd Over a year ago

Now prone to underflow. :-) Consider INT_MIN - 1.

Thomas Sablik Over a year ago

@jvd Where do you see underflow? A is sorted. A[i+2]-A[i+1] and A[i+1]-A[i] return positive values.

jvd Over a year ago

@ThomasSablik You are correct. I forgot that A was sorted.

Thomas Sablik Over a year ago

@UriRaz int i = 0; i < A.size()-2 is an implicit check that A.size() is at least 3 before the loop. Of course you can add redundant checks.

|

Collectives™ on Stack Overflow

How to get rid of the arithmetic overflow

1 Answer 1

10 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

10 Comments

Your Answer

Sign up or log in

Post as a guest

Related