Triangle: Determine if an array includes a triangular triplet (Codility)

Question

This is the Triangle problem from Codility:

A zero-indexed array A consisting of N integers is given.
A triplet (P, Q, R) is triangular if 0 ≤ P < Q < R < N and:

A[P] + A[Q] > A[R],
A[Q] + A[R] > A[P],
A[R] + A[P] > A[Q].

Write a function:

int solution(vector<int> &A);  

that, given a zero-indexed array A consisting of N integers, returns 1 if there exists a triangular triplet for this array and returns 0 otherwise.

For example, given array A such that:
A[0] = 10, A[1] = 2, A[2] = 5, A[3] = 1, A[4] = 8, A[5] = 20 Triplet (0, 2, 4) is triangular, the function should return 1.

Given array A such that:
A[0] = 10, A[1] = 50, A[2] = 5, A[3] = 1
function should return 0.

Assume that:

N is an integer within the range [0..100,000];
each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].

And here is my solution in C++:

int solution(vector<int> &A) {
    if(A.size()<3) return 0;

    sort(A.begin(), A.end());

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

I've checked the comments there and all the solutions seems similar to mine.
However, while others claimed to have gotten 100%, I only got a 93% score.
I got all the tests cases correct EXCEPT for one:

extreme_arith_overflow1
overflow test, 3 MAXINTs

I assume this case has some input like this:
[2147483647, 2147483647, 2147483647]

So I add this to the custom test case, and the answer turns out to be 0 when it clearly should be 1.
I also tried [1900000000, 1900000000, 1900000000], and the answer is still 0.
However, [1000000000, 1000000000, 1000000000] is correct with answer of 1.

Can anyone clue me in on why this result occured?
Greatly appreciated.

Answer 1

My solution in Java with 100/100 and time complexity of O(N*log(N))

With comments explaining the logic

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
import java.util.Arrays;

class Solution {

    public int solution(int[] A) {

    int N = A.length;
    if (N < 3) return 0;
    Arrays.sort(A);

    for (int i = 0; i < N - 2; i++) {

        /**
         * Since the array is sorted A[i + 2] is always greater or equal to previous values
         * So A[i + 2] + A[i] > A[i + 1] ALWAYS
         * As well ass A[i + 2] + A[i + 1] > A[i] ALWAYS
         * Therefore no need to check those. We only need to check if A[i] + A[i + 1] > A[i + 2]?
         * Since in case of A[i] + A[i + 1] > MAXINT the code would strike an overflow (ie the result will be greater than allowed integer limit)
         * We'll modify the formula to an equivalent A[i] > A[i + 2] - A[i + 1]
         * And inspect it there
         */
        if (A[i] >= 0 && A[i] > A[i + 2] - A[i + 1]) {

            return 1;
        }
    }

    return 0;
}

Basically when you check X + Y value of integers, that is greater than integer limit the code will fail on overflow. so instead of checking if X + Y > Z, we can simply check the equivalent statement if X > Z - Y (simple math isn't it?). Alternatively you could always use long but it will be a worse solution memory wise.

Also make sure you skip the negatives as a triangle cannot have a negative side value.

Cheers

Answer 2

Java 100 %:

public int solution(int[] A){
        Arrays.sort(A);

        for(int i=0;i<A.length-2;i++){
            if(  
                 ((long)A[i] + (long)A[i+1] > A[i+2]) &&  
                 ((long)A[i+1] + (long)A[i+2] > A[i]) &&
                 ((long)A[i] + (long)A[i+2] > A[i+1]) 
               )
            return 1;   
        }
        return 0;
    }