[Codility] Lesson10 - Prime and composite numbers: MinPerimeterRectangle

Problem

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

  Copyright 2009–2021 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

 

How to solve

- 정보

정수N: 사각형의 넓이

 

가로 세로 길이 A, B사각형의 넓이를 나타내는 정수 N이 주어질 때,

넓이 Area N = A*B, 

둘레 Perimeter = 2*(A+B) 로 표현할 수 있다. 

 

- 구해야 하는것?

사각형의 넓이를 N으로하는 사각형중, 최소 perimeter(둘레)를 가지는 사각형의 perimeter를 return 한다. 

 

- 예시

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.

문제에 나온 예를 보면 N=30일때, 

A, B 길이가 아래와 같은 사각형을 만들 수 있고, 각각의 둘레의 길이는 아래와 같다.

 

(1, 30) 인 경우, 62 

(2, 15) 인 경우, 34

(3, 10) 인 경우, 26

(5, 6) 인 경우, 22

 

즉, N=30일 때, 4개의 사각형이 만들어질 수 있는데, 

최소 둘레를 가지는 사각형은 가로, 세로 길이 (5, 6)인 둘레 22의 사각형이다. 

따라서 이 경우 22를 return 한다. 

 

 

- 풀이

넓이가 N인 사각형의 변의 길이를 각각 가로 A, 세로 B라고 할때, 

N = A*B로 표현할 수 있다. 

 

1) 가능한 A 구하기 
    A<B라고 가정할 때,

    가능한 A는 A<=sqrt(N) 이며, N%A == 0 인 정수이다. 

2) A에 따른 B구하기
    B = N/A
3) perimeter 구하기
   perimeter = 2*(A+B)

4) 최소 perimeter 업데이트  

   perimeter_min = min(perimeter, perimeter_min) 

Solution(c++)

// you can use includes, for example:
#include <bits/stdc++.h>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(int N) {
    // write your code in C++14 (g++ 6.2.0)
    int perimeter_min = INT_MAX;

    if(N == 1){
        return 4;
    }
    
    for(int i=1; i<=sqrt(N); i++){
        if(N%i == 0){
            int A = i;
            int B = N/i;
            int perimeter = 2*(A+B);
            perimeter_min = min(perimeter_min, perimeter);
        }
    }

    return perimeter_min;
}

Test Result

app.codility.com/demo/results/trainingTY3CVW-REV/

Test results - Codility