MinPerimeterRectangle

🔗 質問リンク

https://app.codility.com/programmers/lessons/10-prime_and_composite_numbers/min_perimeter_rectangle/start/

問題の説明

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.

⚠▼制限

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

💡 プール(言語:Python)

簡単に解けました.これは全ミネラルウォーターの個数を求める応用問題である.同じルートnサイズのゲートに対して,周長の値を求め,最小値のアルゴリズムを更新する.時間複雑度O(N)O(N)O(N)O(N)

import math

def solution(N):
    minimum = 1000000000 * 4

    for n in range(1, int(math.sqrt(N)) + 1):
        if N % n == 0:
            perimeter = 0
            if n ** 2 == N:
                perimeter = (2 * n) * 2
            else:
                perimeter = (n + (N // n)) * 2

            if perimeter < minimum:
                minimum = perimeter

    return minimum