Codility ‘MinPerimeterRectangle’ Solution

Short Problem Definition:

Find the minimal perimeter of any rectangle whose area equals N.

Link

MinPerimeterRectangle

Complexity:

expected worst-case time complexity is O(sqrt(N));

expected worst-case space complexity is O(1).

Execution:

Trivial search for the largest prime.

Solution:
import math
def solution(N):
    if N <= 0:
      return 0
  
    for i in xrange(int(math.sqrt(N)), 0, -1):
        if N % i == 0:
            return 2*(i+N/i)
            
    raise Exception("should never reach here!")    

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
  • João Prudêncio

    Hi Martin, can you explain how do you reached this conclusion “Trivial search for the largest prime.”?

    • Hi Joao, the smallest perimeter with a given area is achieved by an object that is as close to a square as possible. Codility gives an example with an area of 30. There you can see that 5×6 has a smaller perimeter (22) than 1×30 (62). This rule holds for all cases. Therefore finding the largest prime smaller or equal to sqrt(N) gives you the smaller side of the rectangle. Just calculate the other side (which can be either equal in case of a square, or bigger in case of a rectangle). Sqrt(30) = 5.47722. Smallest prime is 5. 30/5 = 6. Your smallest perimeter is a rectangle 5×6

      • Funkdafied

        It happens that 5 is a prime but there is no reason the answer always has to be prime. E.g. If the area was 24, the answer would be a 4×6 rectangle