def maximumPerimeterTriangle(sticks): triangles = [] # Go through the numbers from largest to smallest. # Return the first non-degenerate triple found, it will be the largest. sorted_sticks = sorted(sticks) for i in reversed(range(len(sorted_sticks) - 2)): side_1 = sorted_sticks[i+2] side_2 = sorted_sticks[i+1] side_3 = sorted_sticks[i] if (side_2 + side_3 > side_1): return side_3, side_2, side_1 return [-1]
C++ Solution (8/12 cases passed only)
bool isPossibleTriangle(vector& sticks, int& i, int& j, int& k) { if( (sticks[i] + sticks[j] > sticks[k]) && (sticks[k] + sticks[j] > sticks[i]) && (sticks[i] + sticks[k] > sticks[j]) ) { return true ; } else return false ; }
void solve(vector< pair< int,pair > >& triangles, vector& sticks, int pos1, int pos2, int pos3) { int size = sizeof(sticks)/ sizeof(sticks[0]) ; while(pos1 < size-2) { while(pos2 < size-1) { while(pos3 < size) { if(isPossibleTriangle(sticks, pos1, pos2, pos3)) { pair inner = make_pair(sticks[pos2],sticks[pos3]) ; pair > p = make_pair(sticks[pos1],inner) ; triangles.push_back(p) ; } pos3 ++ ; } pos2 ++ ; pos3 = pos2+1 ; } pos1 ++ ; pos2 = pos1 + 1 ; pos3 = pos2 + 1 ; } } vector maximumPerimeterTriangle(vector sticks) { int n = sticks.size() ;
//Check for minimum sides vector <int> sidesOfAns ; if(n < 3) { sidesOfAns.push_back(-1) ; return sidesOfAns ; } //Request for sorting sticks in non-decreasing bool flag = 0 ; for(int i = 0; i < sticks.size()-1; i++) if(sticks[i] > sticks[i+1]) { flag = 1 ; break ; } if(flag == 1) { sort(sticks.begin(), sticks.end()) ; } //Request for making pairs of pairs of(three ) sticks for each triangle vector< pair< int,pair<int,int> > > triangles ; solve(triangles, sticks, 0, 1, 2) ; //Request for showing possible Triangles //Finding max perimeter && number of times max perimeter occurs && store vector< pair< int,pair<int,int> > > possibleSolutios ; int maxPeri = INT_MIN, maxPeriCount = 0 ; for(int i = 0; i < triangles.size(); i++) { if( (triangles[i].first + triangles[i].second.first + triangles[i].second.second) > maxPeri) { maxPeri = (triangles[i].first + triangles[i].second.first + triangles[i].second.second) ; //delete old saved possible maxima if(possibleSolutios.size() > 0) possibleSolutios.clear() ; //Make pairs of current three side values pair <int,int> inner = make_pair(triangles[i].second.first,triangles[i].second.second) ; pair <int, pair<int,int> > p = make_pair(triangles[i].first, inner) ; //Save the pairs on possibleSolutios possibleSolutios.push_back(p) ; maxPeriCount = 1 ; } else if( (triangles[i].first + triangles[i].second.first + triangles[i].second.second) == maxPeri ) { //Just save && increase count, count to check later for more problems pair <int,int> inner = make_pair(triangles[i].second.first,triangles[i].second.second) ; pair <int, pair<int,int> > p = make_pair(triangles[i].first, inner) ; possibleSolutios.push_back(p) ; maxPeriCount++ ; } } //Only one max sum of sides if(maxPeriCount == 1) { sidesOfAns.push_back(possibleSolutios[0].first) ; sidesOfAns.push_back(possibleSolutios[0].second.first) ; sidesOfAns.push_back(possibleSolutios[0].second.second) ; return sidesOfAns ; } //Check for maximum side equality vector< pair< int,pair<int,int> > > possibleMaxEqualSolutions ; int maxSideCount = 0, maxSide = INT_MIN ; for(int i = 0; i < maxPeriCount; i++) { if(possibleSolutios[i].second.second > maxSide) { maxSide = possibleSolutios[i].second.second ; //delete old saved possible maxima if(possibleMaxEqualSolutions.size() > 0) possibleMaxEqualSolutions.clear() ; //Make pairs of current three side values pair <int,int> inner = make_pair( possibleSolutios[i].second.first, possibleSolutios[i].second.second ) ; pair <int, pair<int,int> > p = make_pair( possibleSolutios[i].first, inner) ; //Save the pairs on possibleMax(Side)EqualSolutios possibleMaxEqualSolutions.push_back(p) ; maxSideCount = 1 ; } else if(possibleSolutios[i].second.second == maxSide) { //Just save && increase count, count to check later for more problems pair <int,int> inner = make_pair( possibleSolutios[i].second.first, possibleSolutios[i].second.second ) ; pair <int, pair<int,int> > p = make_pair( possibleSolutios[i].first, inner ) ; possibleMaxEqualSolutions.push_back(p) ; maxSideCount++ ; } } //Check how many triangles have equal max sides if(maxSideCount == 1) { sidesOfAns.push_back(possibleMaxEqualSolutions[0].first) ; sidesOfAns.push_back(possibleMaxEqualSolutions[0].second.first) ; sidesOfAns.push_back(possibleMaxEqualSolutions[0].second.second) ; return sidesOfAns ; } //Check for maximum side equality vector< pair< int,pair<int,int> > > possibleMaxMINEqualSolutions ; int MINmaxSideCount = 0, MINmaxSide = INT_MAX ; for(int i = 0; i < maxSideCount; i++) { if(possibleMaxEqualSolutions[i].second.second < MINmaxSide) { MINmaxSide = possibleMaxEqualSolutions[i].second.second ; //delete old saved possible maxima if(possibleMaxMINEqualSolutions.size() > 0) possibleMaxMINEqualSolutions.clear() ; //Make pairs of current three side values pair <int,int> inner = make_pair( possibleMaxEqualSolutions[i].second.first, possibleMaxEqualSolutions[i].second.second ) ; pair <int, pair<int,int> > p = make_pair( possibleMaxEqualSolutions[i].first, inner) ; //Save the pairs on possibleMax(Side)EqualSolutios possibleMaxMINEqualSolutions.push_back(p) ; MINmaxSideCount = 1 ; } else if(possibleMaxEqualSolutions[i].second.second == MINmaxSide) { //Just save && increase count, count to check later for more problems pair <int,int> inner = make_pair( possibleMaxEqualSolutions[i].second.first, possibleMaxEqualSolutions[i].second.second ) ; pair <int, pair<int,int> > p = make_pair( possibleMaxEqualSolutions[i].first, inner ) ; possibleMaxMINEqualSolutions.push_back(p) ; MINmaxSideCount++ ; } } //Take any available minima + x + maxima (sided) triangle //Check how many triangles have equal max sides if(MINmaxSideCount >= 1) { sidesOfAns.push_back(possibleMaxMINEqualSolutions[0].first) ; sidesOfAns.push_back(possibleMaxMINEqualSolutions[0].second.first) ; sidesOfAns.push_back(possibleMaxMINEqualSolutions[0].second.second) ; return sidesOfAns ; } else { sidesOfAns.push_back(-1) ; return sidesOfAns ; }}
Mine solutions:
from itertools import combinations def maximumPerimeterTriangle(sticks): # Write your code here # bruteforce way ls=list(filter(lambda x:x[0]+x[1]>x[2] and x[0]+x[2]>x[1] and x[1]+x[2]>x[0],list(combinations(sorted(sticks), 3)))) ls_s=tuple(map(lambda x:(x, sum(x)), ls)) return [-1] if not ls_s else list(max(ls_s)[0])
js
function maximumPerimeterTriangle(s) { s.sort((a,b) => b-a) for (let i=2; i<s.length; i++) { const [a,b,c] = [s[i],s[i-1],s[i-2]]; if (a+b>c) return [a,b,c] } return [-1] }
public static List<Integer> maximumPerimeterTriangle(List<Integer> sticks) { Collections.sort(sticks); int longerPerimeter = Integer.MIN_VALUE; List<Integer> answer = Collections.singletonList(-1); for (int i = 0; i < sticks.size() - 2; i++) { if (sticks.get(i) + sticks.get(i + 1) > sticks.get(i + 2)) { if (sticks.get(i) + sticks.get(i + 1) + sticks.get(i + 2) > longerPerimeter) { longerPerimeter = sticks.get(i) + sticks.get(i + 1) + sticks.get(i + 2); answer = Arrays.asList(sticks.get(i), sticks.get(i + 1), sticks.get(i + 2)); } } } return answer; }
Load more conversations
Sort 272 Discussions, By:
Please Login in order to post a comment