Hackerrank - Maximum Perimeter Triangle Solution
2 min read

Hackerrank - Maximum Perimeter Triangle Solution

Hackerrank - Maximum Perimeter Triangle Solution

Given an array of stick lengths, use  of them to construct a non-degenerate triangle with the maximum possible perimeter. Print the lengths of its sides as  space-separated integers in non-decreasing order.

If there are several valid triangles having the maximum perimeter:

  1. Choose the one with the longest maximum side.
  2. If more than one has that maximum, choose from them the one with the longest minimum side.
  3. If more than one has that maximum as well, print any one them.

If no non-degenerate triangle exists, print -1.

For example, assume there are stick lengths . The triplet  will not form a triangle. Neither will  or , so the problem is reduced to  and . The longer perimeter is .

Function Description

Complete the maximumPerimeterTriangle function in the editor below. It should return an array of  integers that represent the side lengths of the chosen triangle in non-decreasing order.

maximumPerimeterTriangle has the following parameter(s):

  • sticks: an integer array that represents the lengths of sticks available

Input Format

The first line contains single integer , the size of array .
The second line contains  space-separated integers , each a stick length.

Constraints

Output Format

Print the lengths of the  chosen sticks as space-separated integers in non-decreasing order.

If no non-degenerate triangle can be formed, print -1.

Sample Input 0

5
1 1 1 3 3

Sample Output 0

1 3 3

Explanation 0

There are  possible unique triangles:

The second triangle has the largest perimeter, so we print its side lengths on a new line in non-decreasing order.

Sample Input 1

3
1 2 3

Sample Output 1

-1

Explanation 1

The triangle  is degenerate and thus can't be constructed, so we print -1 on a new line.

Sample Input 2

6
1 1 1 2 3 5

Sample Output 2

1 1 1

Explanation 2

The triangle (1,1,1) is the only valid triangle.

Solution in Python

def maximumPerimeterTriangle(a):
    for i in range(0,len(a)-2):
        if a[i]<a[i+1]+a[i+2]:
            return [a[i+2],a[i+1],a[i]]
    return [-1]
input()
a = sorted(map(int,input().split()), reverse=True)
print(*maximumPerimeterTriangle(a))

Note: Sum of any two sides of a triangle is greater than the 3rd side.

Enjoying these posts? Subscribe for more


Adblocker detected! Please consider reading this notice.

We've detected that you are using AdBlock Plus or some other adblocking software which is preventing the page from fully loading.

That's okay. But without advertising-income, we can't keep making this site awesome.

We don't have any banner, Flash, animation, obnoxious sound, or popup ad. We do not implement these annoying types of ads!

We need money to operate the site, and almost all of it comes from our online advertising.

Please add thepoorcoder.com to your ad blocking whitelist or disable your adblocking software.

×