Different time complexity just by changing range

user_3860502 0
Viewed 61

I'm solving the MinPerimeterRectangle problem from Codility:

An integer N is given, representing the area of some rectangle.

The area of a rectangle whose sides are of length A and B is A * B, and the perimeter is 2 * (A + B).

The goal is to find the minimal perimeter of any rectangle whose area equals N. The sides of this rectangle should be only integers.

For example, given integer N = 30, rectangles of area 30 are:

(1, 30), with a perimeter of 62, (2, 15), with a perimeter of 34, (3, 10), with a perimeter of 26, (5, 6), with a perimeter of 22. Write a function:

def solution(N)

that, given an integer N, returns the minimal perimeter of any rectangle whose area is exactly equal to N.

For example, given an integer N = 30, the function should return 22, as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..1,000,000,000].

I initially used this code:

''' import math

def solution(N):
    a = int(math.sqrt(N))
    for i in range (a,N+1):
        if N % i == 0:
            A = int(i)
            B = int(N/i)
            peri = 2*(A+B)
            return(peri)
    pass

'''

Received a total score of 60% and the detected time complexity was O(sqrt(N)). Then just by changing the range in line 6, it improved to 100% for the time complexity.

''' import math

def solution(N):
    a = int(math.sqrt(N))
    for i in range (a,0,-1):
        if N % i == 0:
            A = int(i)
            B = int(N/i)
            peri = 2*(A+B)
            return(peri)
    pass

'''

I noted that for the first one, there were timeout errors when N was a large prime. However, mathematically, I thought the two ranges are of equal length. Why the difference then?

time-complexity
2 Answers

The answer to your question is pretty simple. I assume that you are aware that the minimum of perimeter occurs when the length is equal to breadth meaning that if there was no constraint that l and b have to be natural numbers, you could have twice the square root of your area as your perimeter, but because you have the constraint, both the length and breadth should be as close to each other as possible.

ex: For an area of 30, the minimum perimeter is at (5,6) and for 20, it is at (4,5) and for 12, it is at (3,4).......so on.

Translating this to nerdy computer language would mean that you should get the pair of dimensions in square root of are number of iterations i.e O(n^0.5) which you very well implemented. Now the problem with prime numbers is that they have no other factors apart from one and themselves......meaning that even you started from the square root of the area, you have to iterate all the way up until n or all the way down until 1. For large numbers, iterating back to 1 is easier than iterating up to n (remember that this is n^0.5 and not n/2 and hence the twist). To better explain this you can think of it this way, iterating from 5 to 1 is easier than 5 to 25 and iterating from 8 to 1 is faster than 8 to 64 :).

Hence you were able to find the minimal pair sooner when you iterated down the ladder rather than up. Hope this answers your question.

Happy Coding!

user_121508860

100% Python Solution

Time complexity: (sqrt(N))

This is the link on Codility

import math

def solution(N):

    min_perimeter = 9999999999

    i = 1
    
    while i <= math.sqrt(N) :

        if (N % i == 0):
            perimeter = 2 * (i + int(N/i))
            min_perimeter = min(min_perimeter, perimeter)

        i = i + 1

    return min_perimeter

If someone is looking to understand the idea of getting all divisors of a number: see this

user_121465810
Related