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.

1 2 3 4 5 | def solution(N): from math import sqrt for i in xrange(int(sqrt(N)), 0, -1): if N % i == 0: return 2*(i+N/i) |

Great observation! min(abs(len1,len2))! I didn’t notice it at all!

I wonder what the time complexity of sqrt is? ðŸ™‚

sqrt takes much time. But it is still O(1) or O(logN).

Reference:

http://stackoverflow.com/questions/6884359/c-practical-computational-complexity-of-cmath-sqrt

http://stackoverflow.com/questions/28815339/time-complexity-of-math-sqrt-java

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).

100%, 100% java