Maximum Perimeter Triangle
Maximum Perimeter Triangle
+ 32 comments There's no need to complicate it, here's a simple Python solution :
n = int(input()) A = sorted(int(i) for i in input().split()) i = n-3 while i >= 0 and (A[i] + A[i+1] <= A[i+2]) : i -= 1 if i >= 0 : print(A[i],A[i+1],A[i+2]) else : print(-1)
Logic : Select the longest possible side such that it can form a non-degenerate triangle using the two sides "just smaller" than it.
It fulfills all other conditions. If no such selection is possible, then no non-degenerate triangle exists.
+ 5 comments Java solution:
import java.util.*; public class Solution { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[] a = new int[n]; for(int i = 0; i < n; i++) { a[i] = scanner.nextInt(); } scanner.close(); Arrays.sort(a); int x, y, z; for(x=n-3, y=n-2, z=n-1; a[x]+a[y]<=a[z]; x--, y--, z--){ if(x==0) { System.out.print(-1); return; } } System.out.printf("%d %d %d", a[x], a[y], a[z]); } }
+ 0 comments Java solution - passes 100% of test cases
From my HackerRank solutions.
Hint: Sort the sticks
Time complexity: O(n log n)
import java.util.Scanner; import java.util.Arrays; import java.util.Collections; public class Solution { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int N = scan.nextInt(); Integer [] stick = new Integer[N]; for (int i = 0; i < N; i++) { stick[i] = scan.nextInt(); } scan.close(); findTriangle(stick); } /* Greedy Approach: Try to use the biggest sticks first */ private static void findTriangle(Integer [] stick) { Arrays.sort(stick, Collections.reverseOrder()); for (int i = 0; i < stick.length - 2; i++) { if (stick[i] < stick[i+1] + stick[i+2]) { System.out.println(stick[i+2] + " " + stick[i+1] + " " + stick[i]); return; } } System.out.println(-1); } }
Let me know if you have any questions.
+ 4 comments Non-generate triangle happens when a side of triangle exceed the sum of the other 2 sides. Imagine a triangle with side of 1, 1, and 2; it becomes a line, not a triangle :p. This is the function check the non-generate with input of integer a, b, c where a <= b <= c:
bool isvalid(int a, int b, int c){ return a+b>c; }
then the problem become sorting followed by triangle validation.
int n; cin>>n; vector<int> v(n); for(int i = 0; i<n; ++i){ cin>>v[i]; } sort(v.begin(), v.end(), /* descending */); for(int i = 2; i<n; ++i){ if(isvalid(v[i], v[i-1], v[i-2])){ cout<<v[i]<<" "<<v[i-1]<<" "<<v[i-2]<<endl; return 0; } } cout<<-1<<endl; return 0;
+ 0 comments Java implementation with comments:
static int[] maximumPerimeterTriangle(int[] s) { // Triangle inequality theorem states that // for any non-degenerate triangle, the sum // of the lengths of any two sides must be // greater than the length of the remaining // side. // Sort sticks in ascending order. Arrays.sort(s); // Reverse sticks in decending order. for(int left = 0 ; left < s.length / 2; left++) { int right = s.length - 1 - left; int tmp = s[left]; s[left] = s[right]; s[right] = tmp; } // Go through the sticks in // descending order. for(int i = 0 ; i < s.length - 2 ; ++i) { if (s[i] < s[i+1] + s[i+2]) { // This is a non-degenerate triangle. // Because we ordered the sticks // in descending order this // triangle must have the maximum // perimeter. return new int[] { s[i+2], s[i+1], s[i] }; } } return new int[] { -1 }; }
Sort 270 Discussions, By:
Please Login in order to post a comment