Task score : 100% -  Correctness : 100% ; Performance : 100%

Detected time complexity : O(sqrt(N))

Lesson 10 at app.codility.com/programmers

The solution and its explanation are given below. 

Category of Article : Technology | Computers and Software | Algorithm

Problem

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

Note

The lesson for this problem is Prime and Composite Numbers. So it should occur to the candidate that the knowledge of the lesson is required here. It is assumed that the reader has read the lesson, and has done the previous test before coming here.

The different possible sides for N, are the different possible paired factors of N. When N is 30; 

the factors 1 and 30, give 2x(1+30) = 62, which is the maximum perimeter;

the factors 2 and 15, give 2x(2+15) = 34, which is less than the maximum perimeter;

the factors 3 and 10, give 2x(3+10) = 26, which is less than the previous perimeter;

the factors 5 and 6, give 2x(5+6) = 22, which is the minimal perimeter.

The square root of 30 is 5.48. Remember that factors of an integer occur in pairs: one below and one above the square root (or are both the square root). No lower factor for 30 occurs between 5 and 5.48. So the factors that are closest and around the square root of N, give the minimal perimeter. If N is a perfect square, the minimum perimeter is 2 x (√N+√N). 

Smart Solution

A solution() function is in the following program (read the code and comments):

<?php
function solution($N) {
    $minPeri = 2*(1+$N);    //the maximum perimeter
    $i = 1;

    while ($i * $i < $N) {
        if ($N % $i == 0) 
            $minPeri = 2*($i + $N/$i);
        $i++;
    }

    if ($i * $i == $N)
        $minPeri = 2*($i + $i);    //perfect square 

    return $minPeri;
}

$ret = solution(30);
echo $ret . "\n";
?>

A perimeter is obtained as soon as a pair of factors are obtained. The smallest perimeter at the end is returned. The output is:

    22 

for an input of 30.

At app.codility.com/programmers the scoring and detected time complexity for this solution() is: 

    Task score : 100% -  Correctness : 100% ; Performance : 100%

    Detected time complexity : O(sqrt(N))

Thanks for reading.