Test results - Codility

Tasks Details

easy

1. MinPerimeterRectangle

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

100%

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:

int solution(int 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].

Solution

Programming language used C

Time spent on task 16 minutes

Notes

not defined yet

Task timeline

Code: 10:28:52 UTC, c, verify, result: Passed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");

#include <math.h>

int solution(int N) 
{
    int a;
    
    int sqrtN = sqrt(N);
    int min = 1 + N; //the initial value for the min.
    for (a = 2; a <= sqrtN; a++){
        if (N % a == 0){
            int b = N / a;
            min = a + b < min ? a + b : min;
        }
        
    }
    
    return min * 2;
}

Analysis

▶

example
example test

✔

Code: 10:28:58 UTC, c, verify, result: Passed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");

#include <math.h>

int solution(int N) 
{
    int a;
    
    int sqrtN = sqrt(N);
    int min = 1 + N; //the initial value for the min.
    for (a = 2; a <= sqrtN; a++){
        if (N % a == 0){
            int b = N / a;
            min = a + b < min ? a + b : min;
        }
        
    }
    
    return min * 2;
}

Analysis

▶

example
example test

✔

Code: 10:29:03 UTC, c, final, score: 100

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");

#include <math.h>

int solution(int N) 
{
    int a;
    
    int sqrtN = sqrt(N);
    int min = 1 + N; //the initial value for the min.
    for (a = 2; a <= sqrtN; a++){
        if (N % a == 0){
            int b = N / a;
            min = a + b < min ? a + b : min;
        }
        
    }
    
    return min * 2;
}

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

O(sqrt(N))

▶

example
example test

✔

▶

extreme_min
N = 1 test

✔

▶

simple1
N = 36 test

✔

▶

simple2
N = 48 test

✔

▶

simple3
N = 101 test

✔

▶

small
N = 1,234 test

✔

▶

medium
N = 4,564,320 test

✔

▶

prime1
N = 15,486,451 test

✔

▶

square
N = 100,000,000 test

✔

▶

prime2
N = 982,451,653 test

✔

▶

extreme_max
N = 1,000,000,000 test

✔