Solution to Min-Perimeter-Rectangle by codility

26 Jan

Question: http://codility.com/demo/take-sample-test/min_perimeter_rectangle

Question Name: MinPerimeterRectangle

Let the length of one side be len_1, and the length of one adjacent side be len_2. For a rectangle with a constant area, the perimeter is minimized when the difference between len_1 and len_2, abs(len_1- len_2), is minimized.

4 Replies to “Solution to Min-Perimeter-Rectangle by codility

  1. Great observation! min(abs(len1,len2))! I didn’t notice it at all!
    I wonder what the time complexity of sqrt is? 🙂

    • Exactly my question too. I tried something very similar to Sheng’s solution, importing the math module and using sqrt(). Codility marked it only as 80%, because of apparent poor performance with large numbers. Codility says this takes O(sqrt(N)) time, however. My PyCharm takes only 0.004 seconds even for large numbers but whatever.
      I felt it’s not obvious why the smallest sum of sides is related to the square root, at least not to me. Other comments simply state this as a fact without providing an explanation. Which should be short if it’s that simple. So I first provided a mathematical proof that this is the case.

      What got 100% was simply going through each integer number till you reach the square root. Which also has a time of O(sqrt(N)), obviously, but Codility thinks this is better than using math.sqrt(N).

  2. 100%, 100% java

Leave a Reply

Your email address will not be published. Required fields are marked *

Please put your code into a <pre>YOUR CODE</pre> section. Thanks and Happy Coding!