Triangle : Determine whether a triangle can be bui

Question

I have found a solution on the net for the codility problem below :

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].

For example, consider 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.

Write a function:

 int solution(int A[], int N);

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.

The solution is like this :

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

But when we sort the array, the original index are no more valid and item in i position can move to j position with j>i or j

The solutin suppose that values that verify assertion (Triangle) is automaticly adjacent in sorted array.

In example array, if we change like this :

A[0] = 10 A[1] = 6 (replace 2) A[2] = 5 A[3] = 1 A[4] = 8 A[5] = 20 Here we get 2 new traingle 10 6 5 and 6 5 8. (and 10 5 8)

We sort : 1 5 6 8 10 20 --> Here, original solution (10,5,8) values are not adjacent (no traingle) but instead we have (5,6,8) and (6 8 10). Then algorithm return 1. It seem that if triangle exist then at least values of one triangle will be adjacent but I doesn't find any proof.

Answer 1

Works 100%, tested with different scenario's.

I think all the possibilities are not covered above solution Combination with P,Q,R

A[0] = 10, A[1] = 2, A[2] = 5, A[3] = 1, A[4] = 8, A[5] = 20

index combination

0+1>2, 1+2>0, 2+0>1

1+2>3, 2+3>1, 3+1>2

....

These are combinations needed to achieve this problem.

//Triangle
    /**
     * A[P] + A[Q] > A[R],
       A[Q] + A[R] > A[P],
       A[R] + A[P] > A[Q]
     */
    public int triangleSolution(int[] A) {
    int status = 0;
    for(int i=0; i<A.length; i++) {
        int[] B = removeTheElement(A, i);
        for(int j=0; j<B.length; j++) {
            int[] C = removeTheElement(B, j);
            for(int k=0; k<C.length; k++) {
                if((A[i] + B[j] > C[k]) &&
                   (B[j] + C[k] > A[i]) &&
                   (C[k] + A[i] > B[j])) {
                    return 1;
                }
            }
        }
    }
    return status;
}

    // Function to remove the element 
    public int[] removeTheElement(int[] arr, int index) 
    { 
        // Create another array of size one less 
        int[] anotherArray = new int[arr.length - 1]; 

        // Copy the elements except the index 
        // from original array to the other array 
        for (int i = 0, k = 0; i < arr.length; i++) { 

            // if the index is 
            // the removal element index 
            if (i == index) { 
                continue; 
            } 

            // if the index is not 
            // the removal element index 
            anotherArray[k++] = arr[i]; 
        } 

        //Java >8
        //IntStream.range(0, arr.length).filter(i -> i != index).map(i -> arr[i]).toArray();

        return anotherArray;
    }

Answer 2

I got %93 for my first try ,it had overflow exception and failed in one test case. then I needed to first convert the values into long then do the mathematical calculation. below is the code.

public static int solution(int[] A) {

    if (A.length < 3)
        return 0;

    Arrays.sort(A);

    for (int i = 0; i < A.length - 2; i++) {
        long p = A[i];
        long q = A[i + 1];
        long r = A[i + 2];

        if ((p + q > r) && (q + r > p) && (r + p > q))
            return 1;

    }

    return 0;

}

Answer 3

It's pretty simple really, and I believe vib to be right but I'll try to put it in a simpler way.

Let us suppose you have three elements that are triangular with values u, v, w, then they have (at least) one maximum value. Let us consider that to be w, so u <= w and v <= w

• The definition of "triangular" is equivalent to u + v > w, because if this is true then any sum containing w will always be greater than the other individual values *
• If you keep track of the new position of w when reordering, you can see that the two elements just before it can be
  • either u and v, so you keep the same triangle,
  • or they can be replaced with other values u' and v', which are greater or equal to u and v but smaller than w, and then u' + v' >= u + v > w, so by our new definition of triangular we have another triangle.

So the existence of a triangle in the array proves that there exists at least one adjacent triangle in the sorted array, which does not have to be the same.

---

* It's completely trivial for positive numbers since w is the max. Here's a general demonstration that does not suppose only positive integers. Our hypothesis are v <= w, u <= w and u + v > w. Let us prove by contradiction that u + w <= v it is impossible.

Supposing u + w <= v, we get by adding v on both sides, u + v + w <= v + v, and since u + v is strictly superior to w by hypothesis, we have w + w < u + v + w <= v + v thus w < v, which is contradicting our hypothesis.

Answer 4

Let A denote the original array and let B denote the sorted array (to avoid confusion)

Let p, q, r be such that they form a triangle. Assume that 0 <= A[p] <= A[q] <= A[r].

Let i be such that B[i+1] = A[q]. Let j be such that B[j] = A[p] and k be such that B[k] = A[r]. Then by definition B[j] + B[i+1] > B[k]. Because B is sorted and j < (i+1) < k we have B[i] + B[i+1] >= B[j] + B[i+1] > B[k] >=B[i+2]. It follows that if you do have a triangle, the algorithm returns true.

Answer 5

My solution gives 100%.

Other solutions have more tests than it is necessary, because after sorting the array A[Q] + A[R] > A[P] AND A[R] + A[P] > A[Q] is always true, so we don't need to test it: A[R] is greater than A[Q] and A[P].

And the problem of overflow can be avoided using A[P] > A[R] - A[Q] instead of A[P] + A[Q] > A[R].

import java.util.*;

class Solution {
    public int solution(int[] A) {
        if (A.length < 3) {
            return 0;
        }
        Arrays.sort(A);
        for (int i = 2; i < A.length; ++i) {
            if (A[i - 2] > A[i] - A[i - 1]) {
              return 1;        
            }
        }
        return 0;
    }
}

Answer 6

My solution in Java was this. It works and solves the problem, but when tested on Codility I got 0%, perhaps because of time complexity. Any ideas on how to improve welcome in the comments, I can edit the answer for all to see:

import java.util.Arrays;

public class Triangular {
    public static int solution(int[] A) {
        // Sort the array and nullify values which won't count. 
        Arrays.sort(A);
        for(int i=0;i<A.length;i++){
            if(A[i]>A.length){
                A[i]=0;
            }
        }

        //Increment the counter, if a triangle exists then this works.
        int count = 1;
        for(int i=1;i<A.length-1;i++){
            if(A[i-1]+A[i+1]>A[i]){
                count++;
            }
        }

        switch(count){
            case 3:
                return 1;
            default:
                return 0;
        }

    }