Form a Triangle

Posted: 8 Nov, 2020
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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.
Approach 1

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.

 

  1. 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.
  2. 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.
  3. 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’.
  4. 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.

Try Problem