Triangle at app.codility.com/programmers in C++ Explained: Determine whether a triangle can be built from a given set of edges.
Task score : 100% - Correctness : 100% ; Performance : 100%
Detected time complexity : O(N * log(N))
Lesson 6 at app.codility.com/programmers
The solution and its explanation are given below.
Category of Article : Technology | Computers and Software | Algorithm
By: Chrysanthus Date Published: 2 Jul 2025
Problem
An 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(vector<int> &A);
that, given an 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
the function should return 1, as explained above. Given array A such that:
A[0] = 10 A[1] = 50 A[2] = 5
A[3] = 1
the function should return 0.
Write an efficient algorithm for the following assumptions:
- 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].
Note
For any existing triangle, the sum of any two sides is bigger than the third side. This has been mentioned in the problem (task) with:A[P] + A[Q] > A[R],
A[Q] + A[R] > A[P],
A[R] + A[P] > A[Q].
where P, Q and R are different indexes, which are not necessarily consecutive. Accept that without proof.
Now, assume that you are given three straight sticks and you are asked if they form a triangle.
It can be shown mathematically, that if the sum of the shorter two sides is greater than the third side, then a triangle can be formed. Accept that without proof. The reader can also consult some other document for these proves, if he/she wishes; or try to prove them himself/herself, by carrying out experiments.
The given vectors (arrays) are:
vector<int> A{10, 2, 5, 1, 8, 20};
and
vector<int> B{10, 50, 5, 1};
Strategy
It can be cumbersome to produce the solution function, the brute-force way. So, only the smart approach is explained here. The question is to know if the list has at least one triplet or no triplet at all. The question is not to know how may triplets exists in the list. It is simply to know if there is at least one triplet in the list. The tutorial (lesson) for this problem is, on sorting. It should occur to the candidate that sorting is required in the solution.So, if the list is sorted in at least O(n.log2n) time, the sorted list can be scanned in O(n) time, comparing three sets of consecutive sides, to know if the sum of the shorter two sides is greater than the third side. If the sum of two smaller numbers in the sorted ascending list, is not bigger than the next third number, then it cannot be bigger than the next fourth number. So, only three consecutive numbers have to be compared continuously, along the list.
The expected time complexity is O(n.log2n + n).
The Code
The program is:#include <iostream>The output is:
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<int> &A) {
int N = A.size();
sort(A.begin(), A.end());
if (N<3)
return 0;
for (int i=0;i<N-2;i++){
if ((long)A[i] + (long)A[i+1] > (long)A[i+2])
return 1;
}
return 0;
}
int main()
{
vector<int> A{10, 2, 5, 1, 8, 20};
int ret = solution(A);
cout << ret <<endl;
vector<int> B{10, 50, 5, 1};
int re = solution(B);
cout << re <<endl;
return 0;
}
1
0
If the number of elements in the list is less than 3, then no triangle can be formed. And so the function should return zero.
Note that after the sorting, the for-loop scans from i=0 to i<N-2, since the next two consecutive elements are checked.
Note that the programmer has not defined his/her own sorting function. The algorithm library provides the sort() function.
Also note that in the body of the for-loop, long integers and not just integers, have been used. The reason is as follows: One of the assumptions in the problem is stated as:
“each element of array A is an integer within the range [-2,147,483,648..2,147,483,647]”
-2,147,483,648 and +2,147,483,647 are the limits of the integer range. Imagine that two shorter sides to be added are 2,147,483,646 and 2,147,483,647. The answer will be 4,294,967,293, which is greater than the highest positive number in the integer range. The sum 4,294,967,293 is already in the long integer range. So long integers have to be used in the addition and comparison, in the for-loop.
At app.codility.com/programmers the scoring and detected time complexity for this smart solution() function is:
Task score : 100% - Correctness : 100% ; Performance : 100%
Detected time complexity : O(N*log(N))
app.codility.com/programmers must have either ignored the O(n) time of the for-loop or has used a sorting function that is faster than O(n.log2n), to have an overall time of O(n.log2n) instead of O(n.log2n + n).
Thanks for reading.