Solution to Min-Perimeter-Rectangle by codility

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? 🙂

   Reply

   • 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

     Reply

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

     1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

     def solution(N):     # Smallest perimeter is made of numbers on either side sqrt(N). That is, the smallest ones, closest ones to sqrt(N).     # This was gleaned by looking at the example case provided.     '''     Mathematical proof:     1. We note all potential scenarios can be sorted according to the following pattern, starting with case a, where     one side is equal to the area and the other side equal to 1.     N = area     N = A * B     a. A = N, B = 1     b. A = N / 2, B = 2 --> Hypothesis says "The sides of this rectangle should be only integers."     So next B can only be 1,     and next one 2, then 3 etc.     c. A = N / 3, B = 3       2. Case a gives Perimeter (P) = (N+1)2 = 2N + 2. Case b, (N/2 + 2)2 = N + 4, c, (N/3 + 3)2 = 2/3*N + 6 etc.     We now try and compare each case to each other.     a > b as:     2N + 2 > 2N / 2 + 4. But our pattern also meets the following     condition: B < A. We don't consider the other half of the set, where B > A, because multiplication is commutative.     Which means A * B = B * A.     So, because B < A, case b means 2 < N / 2. Going back, we get 2N > N + 2. But as we agreed that 2 < N,     2N > N + 2 is always true (qed).     b > c     2N / 2 + 4 > 2N / 3 + 6     N > 2N/3 + 2     The only way 2N/3 + 2 = N is if 2 = N/3;     but 3 < N/3 (B < A), and 2 < 3, so 2 < N/3.     So, 2N/2 + 4 > 2N/3 + 6 is always true (qed).     ...     so each case following will necessarily give a perimeter smaller than the one before.       3. Conclusion: the smallest perimeter is the one for the largest B, where B < A. This is where B < sqrt(N) and     A > sqrt(N).     '''     area = N     if area == 1:         return 4     for i in range(int(math.sqrt(area)), area + 1):         if area % i == 0:             sideA = area / i             sideB = i             break     perimeter = int(2 * (sideA + sideB))     return perimeter

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

     1 2 3 4 5 6 7 8 9 10 11 12 13

     def solution(N):     area = N     if area == 1:         return 4     i = 1     while i * i <= area:         if area % i == 0:             sideA = area / i             sideB = i         i += 1                  perimeter = int(2 * (sideA + sideB))     return perimeter

     Reply

2. 100%, 100% java

   1 2 3 4 5 6 7 8 9 10 11

   public int solution(int N) {         Integer x =  ((Double)Math.sqrt(N)).intValue();         int y = 0 ;         for(int i = x ; x>0 ; x--){             if(N%x == 0){                 y = N/x;                 break;             }         }      return 2*(x+y) ;     }

   Reply