Triangle with the largest perimeter

Easy
0/40
Average time to solve is 10m
profile
Contributed by
23 upvotes
Asked in company
HCL Technologies

Problem statement

You are given an array of positive integers ‘ARR’ of size ‘N’. The task is to return the largest perimeter of a triangle with a non-zero area, having any three elements of ‘ARR’ as its sides. If it’s impossible to form such a triangle, return 0.

Example: 
‘N’ = 4, and ‘ARR’ = [2, 3, 4, 2]

For a triangle, the largest side should be strictly less than the sum of the other two sides. The triplet [2, 2, 4] cannot form a triangle as ‘4 = 2 + 2’. Here, two valid triangles can be formed, having sides as:
1. [2, 3, 4], with perimeter ‘9’.
2. [2, 2, 3], with perimeter ‘7’.

So, you should return ‘9’ as the answer.
Note: 
The array ‘ARR’ contains at least three integers, i.e., ‘N >= 3’.
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line of input contains an integer ‘T’ which denotes the number of test cases. Then, the ‘T’ test cases follow.

The first line of each test case contains an integer ‘N’ denoting the size of the array ‘ARR’.

The second line of each test case contains ‘N’ integers representing the array ‘ARR’.
Output format: 
For every test case, return the largest perimeter of a triangle that can be formed. If it’s impossible to form any triangle, return 0.
Note: 
You do not need to print anything; it has already been taken care of. Just implement the function.
Constraints: 
1 <= T <= 10
1 <= N <= 10^3
Value of each element of ‘ARR’ ranges from [1, 10^9].

Time limit: 1 sec

Sample input 1:

2
4
3 7 1 5 
3
4 1 1

Sample output 1:

15
0

Explanation of sample input 1:

Test Case 1:

Here, only one valid triangle can be formed, having sides as:
1. [3, 5, 7], with perimeter ‘15’.

So, you should return ‘15’ as the answer.

Test Case 2:

We cannot form a valid triangle from the given input. 
So, you should return ‘0’ as the answer.

Sample input 2:

2
4
3 3 4 2 
4
9 4 6 5

Sample output 2:

10
20
Hint

Try to find all possible triangles.

Approaches (2)
Brute force

Let’s say the lengths of three sides of a triangle are ‘A’, ‘B’, and ‘C’, with ‘A <= B <= C’. Then, the condition for these lengths to form a valid triangle with a non-zero area is ‘C < A + B’, i.e., the length of the largest side should be less than the sum of lengths of the other two sides.

 

Use a variable to keep track of the maximum perimeter, let’s say ‘RES’. We can use three nested loops over the array ‘ARR’ to generate all possible triangles. In the innermost loop, if the triangle is valid, then update ‘RES’ accordingly.

 

Algorithm:

  • Create an array ‘CUR[3]’. Use it to store the triangle formed in the innermost loop.
  • Set ‘RES = 0’. Use it to store the maximum perimeter.
  • Run a loop where ‘i’ ranges from ‘0’ to ‘N - 3’:
    • Run a loop where ‘j’ ranges from ‘i + 1’ to ‘N - 2’:
      • Run a loop where ‘k’ ranges from ‘j + 1’ to ‘N - 1’:
        • ‘CUR[0] = ARR[i]’.
        • ‘CUR[1] = ARR[j]’.
        • ‘CUR[2] = ARR[k]’.
        • ‘sort(CUR)’. Sort the array in ascending order.
        • If ‘CUR[2] < CUR[1] + CUR[0]’, then ‘CUR’ is a valid triangle:
          • ‘RES = max(RES, CUR[0] + CUR[1] + CUR[2])’.
  • Return ‘RES’ as the answer.
Time Complexity

O(N^3), where ‘N’ is the size of array ‘ARR’.

 

We run three nested loops, each running for ‘O(N)’ iterations. Thus, the time complexity is ‘O(N^3)’.

Space Complexity

O(1),

 

Since we are not using any extra space, space complexity is constant.

Code Solution
(100% EXP penalty)
Triangle with the largest perimeter
Full screen
Console