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
100%, 100% java