Как избавиться от арифметического переполнения

Question

Это код проблемы с треугольником в кодировке, из-за которой я получаю ошибку арифметического переполнения.

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

Он проходит все тесты, за исключением "переполнения extreme_arith_overflow1, 3 MAXINT", в котором говорится, что код возвращает 0, но ожидает 1. Кто-нибудь знает, как это исправить?

Answer 1

Вы храните A.size() в n а затем вы повторяете, пока i<n и доступ A[i+2]. В случае ошибки этоA[A.size()] или даже A[A.size()+1]. Это вне пределов. Зафиксируйте дальность петли.

Следующая проблема возникает, когда сумма больше, чем INT_MAX. Используйте разницу вместо суммы, чтобы избежать переполнения. Помните, что элементы отсортированы с помощью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;
}