MinPerimeterRectangle task javascript solution 100% score on Codility.com

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

This is the third task of Prime and composite numbers lesson serie, it’s tagged with the flag “painless” and in this article I am going to share with you a javascript solution that gets 100% score in matter of performance and correctness so before we begin here’s the task description on Codility.com:

Codility’s MinPerimeterRectangle task description

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:

function 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].

MinPerimeterRectangle task javascript 100% solution

In this solution I use the same technique as in the previous task “CountFactors” which is to take advantage of the square root of N but before we elaborate this, let’s talk first about how are we going to calculate the minimal perimeter of any rectangle whose area equals N,
knowing that the perimeter of a rectangle is equal 2 * (A + B) and that the area N is equal to A * B which means in other words that A & B are factors of N, we can come to the conclusion that the perimeter of a rectangle is minimal when the difference between the length of the sides A & B is minimal, so the more the value of A is close to the value of B the more we approach to a minimal perimeter and since A & B are factor of N then we already know how we can obtain the most close A & B values and that’s with the help of the square root of N, remember that √n divides all the factors of N into two symmetric groups which means that the more we get close to √n the more we approach to the factors pair that we’re looking for, in other words the A & B we’re looking for are the biggest factor before √n and its symmetric factor: the smallest factor after √n, this is basically the divisors that comes directly before and after √n
if we take the same example as the task description:30 here’s the list of its divisors along with the square root :

1 2 3 5 √30 6 10 15 30

notice that the minimal A & B are found around √n
so the minimal A,B here are 5,6 which are the divisors around √30
now that you understand this, here’s the full code which is a full implementation of what I just explained above

function solution(N) {
    var root=Math.round(Math.sqrt(N))
    for(var i=root;i>=1;i--){
        if(N%i==0){
            var a=i
            var b=N/a
            return 2*(a+b)
        }
    }
}

if you have a better solution or even the same solution but with less lines of code then don’t hesitate to share it with me in the comments below

Also read...

Leave a Reply

Your email address will not be published. Required fields are marked *