Form a Triangle
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

Question

Form a Triangle

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.

Accepted Answer

Sort the array and iterate over it to get the anwer

Accepted Answer

Brute Force

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.

Space Complexity: O(1)Explanation:

O(1).

We are not using any extra space. Thus, the space complexity will be O(1).

Time Complexity: O(n^3)Explanation:

O(N ^ 3), where ‘N’ is the number of elements in the given array/list.

We are pivoting every element as the first side of the triangle and for each first side of the triangle we are going to pivot all the element from next of the first side as the second side of the triangle and for every second side, we are pivoting next element from the second side, as the third side of the triangle. So in the worst case, when there is no triplet that forms a non-degenerate triangle, we have to check all the triplets. Thus, the total time complexity will be O(N ^ 3).

Accepted Answer

Sorting approach

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.

Space Complexity: O(logn)Explanation:

O(log N), where ‘N’ is the number of elements in the given array/list.

We are sorting the given array/list which requires O(log N) recursive stack space. Thus, the total space complexity is O(log N).

Time Complexity: O(nlogn)Explanation:

O(N * log (N)), where ‘N’ is the number of elements in the given array/list.

We are sorting the given array/list which takes O(N log (N) ) time, and then we are iterating through the array/list which requires O(N) time. Thus, the total time complexity will be O(N log(N) ).

Accepted Answer

#include  
bool possibleToMakeTriangle(vector &arr)
{
    // Write your code here.
    int n=arr.size();
    if (n<3) return false;
    sort(arr.begin(),arr.end());
    for(int i=0;iarr[i+2]) return true;
    }
    return false;
}

The code for the above question in c++

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:

Output Format:

Note:

Constraints:

Top PhonePe Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in PhonePe Software Developer