We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Ok, so first we order the list of legs descending by length.
Obviously our first triplet test should just be the first three elements of the list. As the list is ordered, it obviously includes the longest total perimiter, has the longest possible "long leg", as well as the shortest possible "short leg", we can ignore all these first reqs.
Next up we test to see if this triplet is degenerate. This means that leg A + B must be longer than C, and as A >= B >= C, this is automatically true (assuming nonzero input). We also know that A + C > B, as A is at least as big as B, and adding positive C must make it larger. This means we only need to test if B + C > A. If it is, great we are done. However, if not then moving B or C down the list will NOT find a combination that sums greater than A, as B and C are currently at their maximum. This A is simply too large. We can then move A, B, and C down the ordered list of legs all together by one step. This way you would always consider consecutive elements.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Maximum Perimeter Triangle
You are viewing a single comment's thread. Return to all comments →
Ok, so first we order the list of legs descending by length.
Obviously our first triplet test should just be the first three elements of the list. As the list is ordered, it obviously includes the longest total perimiter, has the longest possible "long leg", as well as the shortest possible "short leg", we can ignore all these first reqs.
Next up we test to see if this triplet is degenerate. This means that leg A + B must be longer than C, and as A >= B >= C, this is automatically true (assuming nonzero input). We also know that A + C > B, as A is at least as big as B, and adding positive C must make it larger. This means we only need to test if B + C > A. If it is, great we are done. However, if not then moving B or C down the list will NOT find a combination that sums greater than A, as B and C are currently at their maximum. This A is simply too large. We can then move A, B, and C down the ordered list of legs all together by one step. This way you would always consider consecutive elements.