Codility and other programming lessons: Lesson 4: Triangle (Triangle)
https://codility.com/programmers/lessons/4
Then, we can have A[P] <= A[Q] <= A[R] for any 0 <= P < Q < R < N, as it is sorted in ascending order.
Then, assume all of these are positive values:
(0 < A[P] <= A[Q] <= A[R]).
Because the values are sorted, we can say as follows.
The condition 'A[P] < A[Q] + A[R]' always holds.
The condition 'A[Q] < A[P] + A[R]' also always holds, as 0 <= A[Q] <= A[R].
The condition 'A[R] < A[P] + A[Q]' needs to be checked., yet if we have a certain value R for A[R], we only have to check the two slots right before A[R], each of which as A[P] or A[Q] respectively, is bigger than A[R]. (We only have to if there is any triangular exist or not. as these two values are biggest, we only have to see these two.)
The reason why we can neglect any negative value is as follows.
If A[P] <= 0 <= A[Q] <= A[R], A[P] + A[Q] <= A[Q].
Then, it will be always `A[P] + A[Q] <= A[Q] <= A[R]', thus, 'A[R] < A[P] + A[Q]' is violated.
Thus, after sorting we only have check three consecutive slots from the head to the tail in the array A.
This question also requires us to avoid both overflow and underflow.
{
if (N < 3){
return 0;
}
qsort(A, N, sizeof(int), compare_int);
int i;
for (i = 2; i < N; i++){
int p = A[i - 2];
int q = A[i - 1];
int r = A[i];
//neglect negative values.
if (p <= 0){
continue;
}
//if write like 'r < p + q', 'p + q' may overflow.
if (r - p < q ){
return 1;
}
}
return 0;
}
https://gist.github.com/pranuthi9/b157a3e43224d8aad6da
/ only need check a+b<c, as a<=b<=c, also a+b<c may overflow
public int isTriangle(int a, int b, int c) {
if (a+b > c && b+c > a && c+a > b) {
return 1;
}
else return 0;
}
Read full article from Codility and other programming lessons: Lesson 4: Triangle (Triangle)
https://codility.com/programmers/lessons/4
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.
First, let's sort the array in ascending order.Then, we can have A[P] <= A[Q] <= A[R] for any 0 <= P < Q < R < N, as it is sorted in ascending order.
Then, assume all of these are positive values:
(0 < A[P] <= A[Q] <= A[R]).
Because the values are sorted, we can say as follows.
The condition 'A[P] < A[Q] + A[R]' always holds.
The condition 'A[Q] < A[P] + A[R]' also always holds, as 0 <= A[Q] <= A[R].
The condition 'A[R] < A[P] + A[Q]' needs to be checked., yet if we have a certain value R for A[R], we only have to check the two slots right before A[R], each of which as A[P] or A[Q] respectively, is bigger than A[R]. (We only have to if there is any triangular exist or not. as these two values are biggest, we only have to see these two.)
The reason why we can neglect any negative value is as follows.
If A[P] <= 0 <= A[Q] <= A[R], A[P] + A[Q] <= A[Q].
Then, it will be always `A[P] + A[Q] <= A[Q] <= A[R]', thus, 'A[R] < A[P] + A[Q]' is violated.
Thus, after sorting we only have check three consecutive slots from the head to the tail in the array A.
This question also requires us to avoid both overflow and underflow.
People often write like 'return *(int*)a - *(int*)b;' for the comparator function for C's qsort library function, this can cause underflow. Writing 'r < p + q' may cause overflow when p + q are large.
int solution(int A[], int N) {
if (N < 3){
return 0;
}
qsort(A, N, sizeof(int), compare_int);
int i;
for (i = 2; i < N; i++){
int p = A[i - 2];
int q = A[i - 1];
int r = A[i];
//neglect negative values.
if (p <= 0){
continue;
}
//if write like 'r < p + q', 'p + q' may overflow.
if (r - p < q ){
return 1;
}
}
return 0;
}
https://gist.github.com/pranuthi9/b157a3e43224d8aad6da
/ only need check a+b<c, as a<=b<=c, also a+b<c may overflow
public int isTriangle(int a, int b, int c) {
if (a+b > c && b+c > a && c+a > b) {
return 1;
}
else return 0;
}
Read full article from Codility and other programming lessons: Lesson 4: Triangle (Triangle)
