Maximum Perimeter Triangle from array
Given an array of non-negative integers. Find out three elements from this array that form a triangle of the maximum perimeter.
Examples:
Input : {6, 1, 6, 5, 8, 4}
Output : 20
Input : {2, 20, 7, 55, 1, 33, 12, 4}
Output : Triangle formation is not possible.
Input: {33, 6, 20, 1, 8, 12, 5, 55, 4, 9}
Output: 41
Naive Solution: The brute force solution is: check for all combinations of 3 elements, whether it forms a triangle or not, and update the maximum perimeter if it forms a triangle. The complexity of the naive solution is O(n3). Below is the code for it.
Implementation:
C++
// Brute force solution to find // out maximum perimeter triangle which // can be formed using the elements // of the given array #include <iostream> #include <algorithm> using namespace std; // Function to find out maximum perimeter void maxPerimeter( int arr[], int n){ // initialize maximum perimeter // as 0. int maxi = 0; // pick up 3 different elements // from the array. for ( int i = 0; i < n - 2; i++){ for ( int j = i + 1; j < n - 1; j++){ for ( int k = j + 1; k < n; k++){ // a, b, c are 3 sides of the triangle int a = arr[i]; int b = arr[j]; int c = arr[k]; // check whether a, b, c forms // a triangle or not. if (a < b+c && b < c+a && c < a+b){ // if it forms a triangle // then update the maximum value. maxi = max(maxi, a+b+c); } } } } // If maximum perimeter is non-zero // then print it. if (maxi) cout << "Maximum Perimeter is: " << maxi << endl; // otherwise no triangle formation // is possible. else cout << "Triangle formation " << "is not possible." << endl; } // Driver Program int main() { // test case 1 int arr1[6] = {6, 1, 6, 5, 8, 4}; maxPerimeter(arr1, 6); // test case 2 int arr2[8] = {2, 20, 7, 55, 1, 33, 12, 4}; maxPerimeter(arr2, 8); // test case 3 int arr3[10] = {33, 6, 20, 1, 8, 12, 5, 55, 4, 9}; maxPerimeter(arr3, 10); return 0; } |
Java
// Brute force solution to find out maximum // perimeter triangle which can be formed // using the elements of the given array import java.io.*; class GFG { // Function to find out maximum perimeter static void maxPerimeter( int arr[], int n) { // initialize maximum perimeter as 0. int maxi = 0 ; // pick up 3 different elements // from the array. for ( int i = 0 ; i < n - 2 ; i++) { for ( int j = i + 1 ; j < n - 1 ; j++) { for ( int k = j + 1 ; k < n; k++) { // a, b, c are 3 sides of // the triangle int a = arr[i]; int b = arr[j]; int c = arr[k]; // check whether a, b, c // forms a triangle or not. if (a < b+c && b < c+a && c < a+b) { // if it forms a triangle // then update the maximum // value. maxi = Math.max(maxi, a+b+c); } } } } // If maximum perimeter is non-zero // then print it. if (maxi > 0 ) System.out.println( "Maximum Perimeter is: " + maxi); // otherwise no triangle formation // is possible. else System.out.println( "Triangle formation " + "is not possible." ); } // Driver Program public static void main (String[] args) { // test case 1 int arr1[] = { 6 , 1 , 6 , 5 , 8 , 4 }; maxPerimeter(arr1, 6 ); // test case 2 int arr2[] = { 2 , 20 , 7 , 55 , 1 , 33 , 12 , 4 }; maxPerimeter(arr2, 8 ); // test case 3 int arr3[] = { 33 , 6 , 20 , 1 , 8 , 12 , 5 , 55 , 4 , 9 }; maxPerimeter(arr3, 10 ); } } // This code is contributed by anuj_67. |
Python
# Brute force solution to find # out maximum perimeter triangle # which can be formed using the # elements of the given array # Function to find out # maximum perimeter def maxPerimeter(arr): maxi = 0 n = len (arr) # pick up 3 different # elements from the array. for i in range (n - 2 ): for j in range (i + 1 , n - 1 ): for k in range (j + 1 , n): # a, b, c are 3 sides # of the triangle a = arr[i] b = arr[j] c = arr[k] if (a < b + c and b < a + c and c < a + b): maxi = max (maxi, a + b + c) if (maxi = = 0 ): return "Triangle formation is not possible" else : return "Maximum Perimeter is: " + str (maxi) # Driver code def main(): arr1 = [ 6 , 1 , 6 , 5 , 8 , 4 ] a = maxPerimeter(arr1) print (a) arr2 = [ 2 , 20 , 7 , 55 , 1 , 33 , 12 , 4 ] a = maxPerimeter(arr2) print (a) arr3 = [ 33 , 6 , 20 , 1 , 8 , 12 , 5 , 55 , 4 , 9 ] a = maxPerimeter(arr3) print (a) if __name__ = = '__main__' : main() # This code is contributed # by Pritha Updhayay |
C#
// Brute force solution to find out // maximum perimeter triangle which // can be formed using the elements // of the given array using System; class GFG { // Function to find out // maximum perimeter static void maxPerimeter( int []arr, int n) { // initialize maximum // perimeter as 0. int maxi = 0; // pick up 3 different elements // from the array. for ( int i = 0; i < n - 2; i++) { for ( int j = i + 1; j < n - 1; j++) { for ( int k = j + 1; k < n; k++) { // a, b, c are 3 sides of // the triangle int a = arr[i]; int b = arr[j]; int c = arr[k]; // check whether a, b, c // forms a triangle or not. if (a < b + c && b < c + a && c < a + b) { // if it forms a triangle // then update the maximum // value. maxi = Math.Max(maxi, a + b + c); } } } } // If maximum perimeter is // non-zero then print it. if (maxi > 0) Console.WriteLine( "Maximum Perimeter is: " + maxi); // otherwise no triangle // formation is possible. else Console.WriteLine( "Triangle formation " + "is not possible." ); } // Driver Code public static void Main () { // test case 1 int []arr1 = {6, 1, 6, 5, 8, 4}; maxPerimeter(arr1, 6); // test case 2 int []arr2 = {2, 20, 7, 55, 1, 33, 12, 4}; maxPerimeter(arr2, 8); // test case 3 int []arr3 = {33, 6, 20, 1, 8, 12, 5, 55, 4, 9}; maxPerimeter(arr3, 10); } } // This code is contributed by anuj_67. |
Javascript
<script> // JavaScript program to find // out maximum perimeter triangle which // can be formed using the elements // of the given array // Function to find out maximum perimeter function maxPerimeter(arr, n) { // initialize maximum perimeter as 0. let maxi = 0; // pick up 3 different elements // from the array. for (let i = 0; i < n - 2; i++) { for (let j = i + 1; j < n - 1; j++) { for (let k = j + 1; k < n; k++) { // a, b, c are 3 sides of // the triangle let a = arr[i]; let b = arr[j]; let c = arr[k]; // check whether a, b, c // forms a triangle or not. if (a < b+c && b < c+a && c < a+b) { // if it forms a triangle // then update the maximum // value. maxi = Math.max(maxi, a+b+c); } } } } // If maximum perimeter is non-zero // then print it. if (maxi > 0) document.write( "Maximum Perimeter is: " + maxi + "<br/>" ); // otherwise no triangle formation // is possible. else document.write( "Triangle formation " + "is not possible." + "<br/>" ); } // Driver code // test case 1 let arr1 = [6, 1, 6, 5, 8, 4]; maxPerimeter(arr1, 6); // test case 2 let arr2 = [2, 20, 7, 55, 1, 33, 12, 4]; maxPerimeter(arr2, 8); // test case 3 let arr3 = [33, 6, 20, 1, 8, 12, 5, 55, 4, 9]; maxPerimeter(arr3, 10); // This code is contributed by splevel62. </script> |
PHP
<?php // Brute force solution to find // out maximum perimeter triangle which // can be formed using the elements // of the given array // Function to find out // maximum perimeter function maxPerimeter( $arr , $n ) { // initialize maximum // perimeter as 0. $maxi = 0; // pick up 3 different // elements from the array. for ( $i = 0; $i < $n - 2; $i ++) { for ( $j = $i + 1; $j < $n - 1; $j ++) { for ( $k = $j + 1; $k < $n ; $k ++) { // a, b, c are 3 sides // of the triangle $a = $arr [ $i ]; $b = $arr [ $j ]; $c = $arr [ $k ]; // check whether a, b, c // forms a triangle or not. if ( $a < $b + $c and $b < $c + $a and $c < $a + $b ) { // if it forms a triangle // then update the maximum value. $maxi = max( $maxi , $a + $b + $c ); } } } } // If maximum perimeter is // non-zero then print it. if ( $maxi ) { echo "Maximum Perimeter is: " ; echo $maxi , "\n" ; } // otherwise no triangle // formation is possible. else { echo "Triangle formation " ; echo "is not possible. \n" ; } } // Driver Code // test case 1 $arr1 = array (6, 1, 6, 5, 8, 4); maxPerimeter( $arr1 , 6); // test case 2 $arr2 = array (2, 20, 7, 55, 1, 33, 12, 4); maxPerimeter( $arr2 , 8); // test case 3 $arr3 = array (33, 6, 20, 1, 8, 12, 5, 55, 4, 9); maxPerimeter( $arr3 , 10); // This code is contributed by anuj_67. ?> |
Maximum Perimeter is: 20 Triangle formation is not possible. Maximum Perimeter is: 41
Auxiliary Space : O(1)
Efficient Approach:
First, we can sort the array in non-increasing order. So, the first element will be the maximum and the last will be the minimum. Now if the first 3 elements of this sorted array form a triangle, then it will be the maximum perimeter triangle, as for all other combinations the sum of elements(i.e. the perimeter of that triangle) will be = b >= c). a, b,c can not form a triangle, so a >= b + c. As, b and c = c+d (if we drop b and take d) or a >= b+d (if we drop c and take d). So, we have to drop a and pick up d.
Again, the same set of analysis for b, c, and d. We can continue this till end and whenever we find a triangle forming a triple, then we can stop checking, as this triple gives a maximum perimeter.
Hence, if arr[i] < arr[i+1] + arr[i+2] (0 <= i <= n-3)in the sorted array, then arr[i], arr[i+1] and arr[i+2] form a triangle.
Below is the simple implementation of this concept:
C++
// Efficient solution to find // out maximum perimeter triangle which // can be formed using the elements // of the given array #include <iostream> #include <algorithm> using namespace std; // Function to find out maximum perimeter void maxPerimeter( int arr[], int n){ // sort the array elements // in reversed order sort(arr, arr+n, greater< int >()); // initialize maximum // perimeter to 0 int maxi = 0; // loop through the sorted array // and check whether it forms a // triangle or not. for ( int i = 0; i < n-2; i++){ // Check whether arr[i], arr[i+1] // and arr[i+2] forms a triangle // or not. if (arr[i] < arr[i+1] + arr[i+2]){ // if it forms a triangle then // it is the triangle with // maximum perimeter. maxi = max(maxi, arr[i] + arr[i+1] + arr[i+2]); break ; } } // If maximum perimeter is non-zero // then print it. if (maxi) cout << "Maximum Perimeter is: " << maxi << endl; // otherwise no triangle formation // is possible. else cout << "Triangle formation" << "is not possible." << endl; } // Driver Program int main() { // test case 1 int arr1[6] = {6, 1, 6, 5, 8, 4}; maxPerimeter(arr1, 6); // test case 2 int arr2[8] = {2, 20, 7, 55, 1, 33, 12, 4}; maxPerimeter(arr2, 8); // test case 3 int arr3[10] = {33, 6, 20, 1, 8, 12, 5, 55, 4, 9}; maxPerimeter(arr3, 10); return 0; } |
Java
// Efficient solution to find // out maximum perimeter triangle which // can be formed using the elements // of the given array import java.util.Arrays; class GFG { // Function to find out maximum perimeter static void maxPerimeter( int arr[], int n) { // sort the array elements // in reversed order arr = arrRevSort(arr); //sort(arr, arr+n, greater<int>()); // initialize maximum // perimeter to 0 int maxi = 0 ; // loop through the sorted array // and check whether it forms a // triangle or not. for ( int i = 0 ; i < n - 2 ; i++) { // Check whether arr[i], arr[i+1] // and arr[i+2] forms a triangle // or not. if (arr[i] < arr[i + 1 ] + arr[i + 2 ]) { // if it forms a triangle then // it is the triangle with // maximum perimeter. maxi = Math.max(maxi, arr[i] + arr[i + 1 ] + arr[i + 2 ]); break ; } } // If maximum perimeter is non-zero // then print it. if (maxi > 0 ) { System.out.println( "Maximum Perimeter is: " + maxi); } // otherwise no triangle formation // is possible. else { System.out.println( "Triangle formation is not possible." ); } } //Function return sorted array in Decreasing static int [] arrRevSort( int [] arr) { Arrays.sort(arr, 0 , arr.length); int j = arr.length - 1 ; for ( int i = 0 ; i < arr.length / 2 ; i++, j--) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } return arr; } // Driver Program public static void main(String[] args) { // test case 1 int arr1[] = { 6 , 1 , 6 , 5 , 8 , 4 }; maxPerimeter(arr1, 6 ); // test case 2 int arr2[] = { 2 , 20 , 7 , 55 , 1 , 33 , 12 , 4 }; maxPerimeter(arr2, 8 ); // test case 3 int arr3[] = { 33 , 6 , 20 , 1 , 8 , 12 , 5 , 55 , 4 , 9 }; maxPerimeter(arr3, 10 ); } } /*This Java code is contributed by 29AjayKumar*/ |
Python3
# Efficient solution to find # out maximum perimeter triangle which # can be formed using the elements # of the given array # Function to find the # maximum perimeter def maxPerimeter(arr): maxi = 0 n = len (arr) arr.sort(reverse = True ) for i in range ( 0 , n - 2 ): if arr[i] < (arr[i + 1 ] + arr[i + 2 ]): maxi = max (maxi, arr[i] + arr[i + 1 ] + arr[i + 2 ]) break if (maxi = = 0 ): return "Triangle formation is not possible" else : return "Maximum Perimeter is: " + str (maxi) # Driver Code def main(): arr1 = [ 6 , 1 , 6 , 5 , 8 , 4 ] a = maxPerimeter(arr1) print (a) arr2 = [ 2 , 20 , 7 , 55 , 1 , 33 , 12 , 4 ] a = maxPerimeter(arr2) print (a) arr3 = [ 33 , 6 , 20 , 1 , 8 , 12 , 5 , 55 , 4 , 9 ] a = maxPerimeter(arr3) print (a) if __name__ = = '__main__' : main() # This code is contributed # by Pritha Upadhyay |
C#
// Efficient solution to find // out maximum perimeter triangle which // can be formed using the elements // of the given array using System; class GFG { // Function to find out maximum perimeter static void maxPerimeter( int [] arr, int n) { // sort the array elements // in reversed order arr = arrRevSort(arr); //sort(arr, arr+n, greater<int>()); // initialize maximum // perimeter to 0 int maxi = 0; // loop through the sorted array // and check whether it forms a // triangle or not. for ( int i = 0; i < n - 2; i++) { // Check whether arr[i], arr[i+1] // and arr[i+2] forms a triangle // or not. if (arr[i] < arr[i + 1] + arr[i + 2]) { // if it forms a triangle then // it is the triangle with // maximum perimeter. maxi = Math.Max(maxi, arr[i] + arr[i + 1] + arr[i + 2]); break ; } } // If maximum perimeter is non-zero // then print it. if (maxi > 0) { Console.WriteLine( "Maximum Perimeter is: " + maxi); } // otherwise no triangle formation // is possible. else { Console.WriteLine( "Triangle formation is not possible." ); } } //Function return sorted array in Decreasing static int [] arrRevSort( int [] arr) { Array.Sort(arr); int j = arr.Length - 1; for ( int i = 0; i < arr.Length / 2; i++, j--) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } return arr; } // Driver Program public static void Main() { // test case 1 int [] arr1 = {6, 1, 6, 5, 8, 4}; maxPerimeter(arr1, 6); // test case 2 int [] arr2 = {2, 20, 7, 55, 1, 33, 12, 4}; maxPerimeter(arr2, 8); // test case 3 int [] arr3 = {33, 6, 20, 1, 8, 12, 5, 55, 4, 9}; maxPerimeter(arr3, 10); } } /*This Java code is contributed by mits*/ |
Javascript
<script> // Efficient solution to find // out maximum perimeter triangle which // can be formed using the elements // of the given array // Function to find out maximum perimeter function maxPerimeter(arr, n){ // sort the array elements // in reversed order arr.sort( function (a, b){ return a - b}); arr.reverse(); // initialize maximum // perimeter to 0 let maxi = 0; // loop through the sorted array // and check whether it forms a // triangle or not. for (let i = 0; i < n-2; i++){ // Check whether arr[i], arr[i+1] // and arr[i+2] forms a triangle // or not. if (arr[i] < arr[i+1] + arr[i+2]){ // if it forms a triangle then // it is the triangle with // maximum perimeter. maxi = Math.max(maxi, arr[i] + arr[i+1] + arr[i+2]); break ; } } // If maximum perimeter is non-zero // then print it. if (maxi) document.write( "Maximum Perimeter is: " + maxi + "</br>" ); // otherwise no triangle formation // is possible. else document.write( "Triangle formation is not possible." + "</br>" ); } // test case 1 let arr1 = [6, 1, 6, 5, 8, 4]; maxPerimeter(arr1, 6); // test case 2 let arr2 = [2, 20, 7, 55, 1, 33, 12, 4]; maxPerimeter(arr2, 8); // test case 3 let arr3 = [33, 6, 20, 1, 8, 12, 5, 55, 4, 9]; maxPerimeter(arr3, 10); </script> |
PHP
<?php // Efficient solution to find out maximum // perimeter triangle which can be formed // using the elements of the given array // Function to find out maximum perimeter function maxPerimeter(& $arr , $n ) { // sort the array elements in // reversed order rsort( $arr ); // initialize maximum perimeter to 0 $maxi = 0; // loop through the sorted array // and check whether it forms a // triangle or not. for ( $i = 0; $i < $n - 2; $i ++) { // Check whether arr[i], arr[i+1] // and arr[i+2] forms a triangle // or not. if ( $arr [ $i ] < $arr [ $i + 1] + $arr [ $i + 2]) { // if it forms a triangle then // it is the triangle with // maximum perimeter. $maxi = max( $maxi , $arr [ $i ] + $arr [ $i + 1] + $arr [ $i + 2]); break ; } } // If maximum perimeter is non-zero // then print it. if ( $maxi ) { echo ( "Maximum Perimeter is: " ); echo ( $maxi ) ; echo ( "\n" ); } // otherwise no triangle formation // is possible. else { echo ( "Triangle formation " ); echo ( "is not possible." ); echo ( "\n" ); } } // Driver Code // test case 1 $arr1 = array (6, 1, 6, 5, 8, 4); $s = sizeof( $arr1 ); maxPerimeter( $arr1 , $s ); // test case 2 $arr2 = array (2, 20, 7, 55, 1,33, 12, 4); $st = sizeof( $arr2 ); maxPerimeter( $arr2 , $st ); // test case 3 $arr3 = array (33, 6, 20, 1, 8, 12, 5, 55, 4, 9); $st1 = sizeof( $arr3 ); maxPerimeter( $arr3 , $st1 ); // This code is contributed // by Shivi_Aggarwal ?> |
Maximum Perimeter is: 20 Triangle formationis not possible. Maximum Perimeter is: 41
Complexity Analysis:
- Time complexity: O(n*log(n)). This much time is required to sort the array.
- Space complexity: O(1) since constant space is used.
Efficient Approach with Math:
This approach is more on mathematical side. As we discussed the efficient approach above. There we sort the array then simulate the every three elements to get the maximum perimeter but also they should satisfy the a+b>c triangle condition. But this approach is rarely seen. I claim that fibonacci sequence is the almost possible(but it does not satisfy the condition a+b>c) triangle rule satisfying sequence where a+b=c.
According to constraints, we can fix the number of elements we should iterate instead of iterating whole array. For example, If our every element lies in 1e9 then we only need to check the 45 max elements of the array to get the max perimeter and If those 45 don’t give a valid answer then rest of the elements can’t form a triangle. So, As per many Coding platforms, the element value will mostly be <=1e9.
Why only 45 elements?
- fibo(45) is 1134903170. As it is greater than 1e9.
- As it is in 45th place in the sequence.
- In fibo sequence, elements don’t obey the triangle rule but they almost do it. So it is possible to have only 45 elements before a number if our right-most number is at max 1e9. If it is increased then also we can fix it. This trick is helpful in complex triangle problems.
C++
#include <bits/stdc++.h> using namespace std; // Function to find out maximum perimeter int maxPerimeter( int arr[], int n){ // sort the array elements // in reversed order sort(arr, arr+n, greater< int >()); // loop through the sorted array // and check whether it forms a // triangle or not. But we need to // iterate at max 45 elements. for ( int i = 0,j=1; i < n-2 &&j<=45; i++,j++){ // Check whether arr[i], arr[i+1] // and arr[i+2] forms a triangle // or not. if (arr[i] < arr[i+1] + arr[i+2]){ return arr[i]+arr[i+1]+arr[i+2]; } } return 0; } void print( int ans){ // If maximum perimeter is non-zero // then print it. if (ans) cout << "Maximum Perimeter is: " << ans << endl; // otherwise no triangle formation // is possible. else cout << "Triangle formation" << " is not possible." << endl; } // Driver Code int main() { // test case 1 int arr1[6] = {6, 1, 6, 5, 8, 4}; print(maxPerimeter(arr1, 6)); // test case 2 int arr2[8] = {2, 20, 7, 55, 1, 33, 12, 4}; print(maxPerimeter(arr2, 8)); // test case 3 int arr3[10] = {33, 6, 20, 1, 8, 12, 5, 55, 4, 9}; print(maxPerimeter(arr3, 10)); return 0; } |
Java
import java.util.Arrays; import java.util.Collections; public class Main { // Function to find out maximum perimeter static int maxPerimeter( int [] arr, int n) { // sort the array elements in reversed order Integer[] arrInteger = new Integer[n]; for ( int i = 0 ; i < n; i++) { arrInteger[i] = arr[i]; } Arrays.sort(arrInteger, Collections.reverseOrder()); // loop through the sorted array // and check whether it forms a // triangle or not. But we need to // iterate at max 45 elements. for ( int i = 0 , j = 1 ; i < n - 2 && j <= 45 ; i++, j++) { // Check whether arr[i], arr[i+1] // and arr[i+2] forms a triangle // or not. if (arrInteger[i] < arrInteger[i + 1 ] + arrInteger[i + 2 ]) { return arrInteger[i] + arrInteger[i + 1 ] + arrInteger[i + 2 ]; } } return 0 ; } static void print( int ans) { // If maximum perimeter is non-zero // then print it. if (ans != 0 ) { System.out.println( "Maximum Perimeter is: " + ans); } else { // otherwise no triangle formation // is possible. System.out.println( "Triangle formation is not possible." ); } } // Driver Code public static void main(String[] args) { // test case 1 int [] arr1 = { 6 , 1 , 6 , 5 , 8 , 4 }; print(maxPerimeter(arr1, 6 )); // test case 2 int [] arr2 = { 2 , 20 , 7 , 55 , 1 , 33 , 12 , 4 }; print(maxPerimeter(arr2, 8 )); // test case 3 int [] arr3 = { 33 , 6 , 20 , 1 , 8 , 12 , 5 , 55 , 4 , 9 }; print(maxPerimeter(arr3, 10 )); } } // This code is contributed by Dwaipayan Bandyopadhyay |
Python3
# Function to find out maximum perimeter def max_perimeter(arr): # sort the array elements in reversed order arr.sort(reverse = True ) # loop through the sorted array # and check whether it forms a triangle or not. # But we need to iterate at max 45 elements. for i in range ( len (arr) - 2 ): # Check whether arr[i], arr[i+1], and arr[i+2] forms a triangle or not. if arr[i] < arr[i + 1 ] + arr[i + 2 ]: return arr[i] + arr[i + 1 ] + arr[i + 2 ] return 0 # Function to print the result def print_result(ans): # If maximum perimeter is non-zero then print it. if ans: print ( "Maximum Perimeter is:" , ans) # otherwise no triangle formation is possible. else : print ( "Triangle formation is not possible." ) # Test cases arr1 = [ 6 , 1 , 6 , 5 , 8 , 4 ] print_result(max_perimeter(arr1)) arr2 = [ 2 , 20 , 7 , 55 , 1 , 33 , 12 , 4 ] print_result(max_perimeter(arr2)) arr3 = [ 33 , 6 , 20 , 1 , 8 , 12 , 5 , 55 , 4 , 9 ] print_result(max_perimeter(arr3)) |
C#
using System; class Program { // Function to find out maximum perimeter static int MaxPerimeter( int [] arr) { // Sort the array elements in reversed order Array.Sort(arr, (a, b) => b.CompareTo(a)); // Loop through the sorted array // and check whether it forms a // triangle or not. But we need to // iterate at max 45 elements. for ( int i = 0, j = 1; i < arr.Length - 2 && j <= 45; i++, j++) { // Check whether arr[i], arr[i+1] // and arr[i+2] forms a triangle // or not. if (arr[i] < arr[i + 1] + arr[i + 2]) { return arr[i] + arr[i + 1] + arr[i + 2]; } } return 0; } static void Print( int ans) { // If maximum perimeter is non-zero // then print it. if (ans != 0) Console.WriteLine( "Maximum Perimeter is: " + ans); // otherwise no triangle formation // is possible. else Console.WriteLine( "Triangle formation is not possible." ); } // Driver Code static void Main() { // Test case 1 int [] arr1 = { 6, 1, 6, 5, 8, 4 }; Print(MaxPerimeter(arr1)); // Test case 2 int [] arr2 = { 2, 20, 7, 55, 1, 33, 12, 4 }; Print(MaxPerimeter(arr2)); // Test case 3 int [] arr3 = { 33, 6, 20, 1, 8, 12, 5, 55, 4, 9 }; Print(MaxPerimeter(arr3)); } } |
Javascript
// Function to find out maximum perimeter function maxPerimeter(arr) { // Sort the array elements in descending order arr.sort((a, b) => b - a); // Loop through the sorted array to check for triangle formation for (let i = 0; i < arr.length - 2; i++) { // Check if arr[i], arr[i+1], and arr[i+2] can form a triangle if (arr[i] < arr[i + 1] + arr[i + 2]) { return arr[i] + arr[i + 1] + arr[i + 2]; } } return 0; } // Function to print the result function printResult(ans) { // If maximum perimeter is non-zero then print it. if (ans) { console.log( "Maximum Perimeter is:" , ans); } else { console.log( "Triangle formation is not possible." ); } } // Test cases let arr1 = [6, 1, 6, 5, 8, 4]; printResult(maxPerimeter(arr1)); let arr2 = [2, 20, 7, 55, 1, 33, 12, 4]; printResult(maxPerimeter(arr2)); let arr3 = [33, 6, 20, 1, 8, 12, 5, 55, 4, 9]; printResult(maxPerimeter(arr3)); |
Output:
Maximum Perimeter is: 20
Triangle formation is not possible.
Maximum Perimeter is: 41
Time Complexity: O(NlogN + 45)
Space Complexity: O(1)
Contact Us