Codility ‘MinPerimeterRectangle’ Solution

Posted on by
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

  • now__what

    I did the same way, however It doesn’t handle it very well if N is a huge prime, as in the “prime2” Performance test on the result screen. I got a TIMEOUT ERROR on that test. Do you (or anyone else) have any idea on how to handle that case? I think it would be too cumbersome/slow to start with deciding if it’s prime e.g. by calculating all primes from 1:N.

    • Calculating all primes up to N using Sieve might be worth the effort if you use it more than once. Using Sieve visits every element at least once O(n*loglogn), so you get no performance benefit for a single pass.

      I doubt prime factorisation will give you better results, but you might want to investigate.

      This leaves me with the conclusion that you might need to micro-optimise the test (which is normally handled by the optimiser, but god knows what optimisation flags are turned on). SQRT is an expensive operation, usually when you iterate bottom-up replacing it by i*i makes the difference. You could also try to tweak the modulus, but I doubt you can get anything out of there. Replacing the size of the step with-2? Unwinding the loop?