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.

Solution 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

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

Solution 3

Here's my clean solution in Python. I got a 100% in Codility. This logic can be adapted to any other programming language.

Note: If the array is sorted, you only have to check that the sum of two consecutive elements is greater than the next element (A[i] + A[i+1] > A[i+2]), because in that case, the other two conditions (A[i+1]+A[i+2] > A[i], A[i]+A[i+2] > A[i+1]) will always be true.

I hope it helps.

def solution(A):

    #edge case check
    if len(A) < 3:
        return 0

    A.sort()
    for i in range(len(A)-2):
        if A[i]+A[i+1] > A[i+2]:
            return 1
    return 0

Solution 4

There are couple of issues here

1. Side of a triangle can't be 0, since it is a length. You have to add that check or you'll fail that corner case. i.e. Wouldn't get 100%.

2. Since you can have an input array of all INT_MAX or LONG_MAX (see http://www.cplusplus.com/reference/climits/), you need to store the sum in a double or long long.

3. You don't have to check all three conditions here i.e.

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

   If you have sorted the array than

   A[Q] + A[R] > A[P] &&
   A[R] + A[P] > A[Q]

   are always true because 0 ≤ P < Q < R i.e. R is greater than P and Q. So you should only check for A[P] + A[Q] > A[R].

You have already placed a check for A.size() < 3 so that is good. I have added a C implementation at https://github.com/naveedrasheed/Codility-Solutions/blob/master/Lesson6_Sorting/triangle.c. You can compare it with solution.

Solution 5

I have used 3 for loop here( without sorting the array) to solve this problem.

public static int solution(int[] A) {

    for (int p = 0; p < A.length; p++) {
        for (int q = p + 1; q < A.length; q++) {
            for (int r = q + 1; r < A.length; r++) {

                if ((A[p] + A[q] > A[r]) && (A[q] + A[r] > A[p]) && (A[r] + A[p] > A[q])) {
                    System.out.println(A[p] + "  " + A[q] + " " + A[r]);
                    return 1;
                }
            }
        }
    }
    return 0;
}

View more solutions