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.
GOOD SOLUTION (93% score, time complexity O(N*log(N))
class Solution {
public int solution(int[] A) {
Array.Sort(A);
if (A.Length <3) return 0;
for (int i=0 ; i<A.Length-2 ; i++)
{ if (A[i] + A[i+1] > A[i+2] )
{return 1;
break;
}
}
return 0;
}
}
I made one mistake here which I realised only once all the test results were ran: I didn't account if the triplet is formed by 3 maxValue integers (C# will wraparound the result of the sum of two maxValues).
BETTER SOLUTION (100% score, time complexity O(N*log(N)))
class Solution {
public int solution(int[] A) {
Array.Sort(A);
if (A.Length <3) return 0;
for (int i=0 ; i<A.Length-2 ; i++)
{ if (A[i] + A[i+1] > A[i+2] )
{
return 1;
break;
}
if (A[i] == A[i+2] &&
A[i+2] == A[i+1] &&
A[i] == Int32.MaxValue)
{
return 1;
break;
}
}
return 0;
}
}
PR
Regarding the Check for the integer overflow. In your is specifically tailored for the the one test in the codility challenge which checks for the overflow and the last value of the triangle equals to Int32.MaxValue. A more general solution to the problem would be to check if the first two values (i, i+1) added equals a negative number, which would give away that its an overflow, if the last number (i+2) is positive, its still a valid triangle.
ReplyDeleteFor the overflow, you can also convert the A[i] + A[i + 1] to a long, my two cents.
ReplyDeleteFor example...https://app.codility.com/demo/results/trainingVRXJ92-Q4A/
There is no need for the above solutions. However, there is a more efficient way of getting the same result. You could just check if A[i] == int.MaxValue, instead of all three numbers. The array is sorted, so if the first one is max, then the rest are DEFINITELY max as well.
ReplyDelete