http://www.martinkysel.com/codility-triangle-solution/
Determine whether a triangle can be built from a given set of edges.
http://blog.nkbits.com/2015/07/19/codility-triangle/
Determine whether a triangle can be built from a given set of edges.
By sorting the array, we have guaranteed that P+R > Q and Q+R > P (because R is always the biggest). Now what remains, is the proof that P+Q > R, that can be found out by traversing the array. The chance to find such a combination is with three adjacent values as they provide the highest P and Q.
def solution(A): if len(A) < 3: raise Exception("invalid input") A.sort() for i in xrange(len(A)-2): if A[i] + A[i+1] > A[i+2]: return 1 return 0
public int solution(int[] A) {
// Handle with the special cases
if(null == A || A.length < 3) return 0;
// Sort the input, and then try to find the triangular
Arrays.sort(A);
for(int i = 0; i < A.length-2; i++) {
// Beware of overflow
if (A[i] >= 0 && A[i] > A[i+2] - A[i+1]) {
return 1;
}
/*
* We already know A[i+1] <= A[i+2]. If A[i] < 0,
* A[i] + A[i+1] < A[i+2]
*/
}
return 0;
}
