Last Updated: 8 Nov, 2020
Form a Triangle
Easy
Asked in companies
You are given an integer of array/list 'ARR' of length ‘N. You are supposed to return true if it is possible to construct at least one non-degenerate triangle using values of array/list as sides of the triangle, otherwise, return false.
Input Format:
The first line contains a single integer ‘T’ denoting the number of test cases. The test cases follow.
The first line of each test case contains a single integer ‘N’ denoting the number of elements in the array.
The second line contains ‘N’ single space-separated integers denoting the elements of the array/list.
Output Format:
For each test case, print a single line containing either “YES”(without quotes) if it is possible to form a non-degenerate triangle, otherwise “NO”(without quotes).
The output of each test case will be printed in a separate line.
Note:
You don’t need to print anything; It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 100
3 <= N <= 10 ^ 3
0 <= ARR[i] <= 10 ^ 9
Where ‘T’ denotes the number of test cases, ‘N’ denotes the number of elements in the array, and 'ARR[i] denotes the elements of the array.
Time Limit: 1 sec.
Approaches
Suppose that 'X', 'Y' and 'Z' are the sides of a triangle, so a non-degenerate triangle can be formed if the following three conditions are satisfied:
- 'X' + 'Y' > 'Z'
- 'Y' + 'Z' > 'X'
- 'X' + 'Z' > 'Y'
The idea is to explore all the possible ways of choosing 3 elements from the given array/list and check if any combination satisfies the constraints for making a non-degenerate triangle or not.
- We will Iterate through the array and pivot each element as the first side of the triangle. Let’s say we are at ‘I’ th index, So we will pivot ‘I’th index as our first side of the triangle.
- And for the second side of the triangle, we will start exploring from the next index of ‘I’ and pivot each element from (I+1) till the end as the second side of the triangle. Let’s say we are at the ‘J’th index, So we will pivot the ‘J’th index as our second side of the triangle.
- And for the third side of the triangle we will iterate from the next index of ‘J’ till the end of the array/list and pivot each element from (J+1) to till the end as the third side of the triangle, say at index ‘K’.
- For each triplet, we will check whether it satisfies all the conditions for forming a non-degenerate triangle or not, I.e
1. 'ARR'[I] +'ARR'[J] >'ARR'[K]
2. 'ARR'[J] + 'ARR'[K] > 'ARR'[I]
3. 'ARR'[I] + 'ARR'[K] > 'ARR'[J]
If yes, then return true otherwise we will go to the next triplet.
If no triplet can become sides of a non-degenerate triangle, return false.
The idea is to use sorting and check if the element at any index ‘I’ forms a non-degenerate triangle with elements at index 'I'+1 and 'I'+2 or not.
- Sort the array in nondecreasing order.
- Iterate through the array to check if, for any three consecutive elements, the sum of the first 2 elements is greater than the 3rd element. Let’s say our current index is ‘I’, then this is the optimal way of choosing the sides because, if 'ARR'['I'] + 'ARR'['I'+1] <= 'ARR'['I'+2], then 'ARR'['I']+'ARR'['I'+1] will surely be less than all elements which have an index greater than 'I'+2. Hence there is no need to check whether elements with an index greater than 'I'+2 form a non-degenerate triangle or not. Also, since the sum of elements at indices 'I'-1 and 'I' is less than the element at index 'I'+1, the sum of 'ARR'['I'] and any element having an index less than 'I'-1 will surely be less than 'ARR'['I'+1]. Hence there is no need to check whether elements that have an index less than 'I' form a non-degenerate triangle or not.
- Return true if any 3 consecutive elements follow the above condition, otherwise return false.
Similar problems