矩形编码的最小周长

Question

这是任务：

给出一个整数 N，表示某个矩形的面积。

边长为 A 和 B 的矩形的面积为 A * B，周长为 2 * (A + B)。

目标是找到面积等于 N 的任何矩形的最小周长。这个矩形的边应该只是整数。

例如，给定整数 N = 30，面积为 30 的矩形为：

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

写一个函数：

int solution(int N); 

给定一个整数 N，返回任何面积正好等于 N 的矩形的最小周长。

例如，给定一个整数 N = 30，函数应该返回 22，如上所述。

假使，假设：

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

复杂：

    expected worst-case time complexity is O(sqrt(N));
    expected worst-case space complexity is O(1).

这是我对 codility task 的解决方案MInPerimeterRectangle。它工作正常，但如果我们有一个测试用例：“982451653”，编译器会得到一个TIMEOUT ERROR. 这是因为这个矩形的最小周长是由边 A = 1 和 B = 982451653 创建的。

所以我有一个问题。是否有可能使此解决方案更快？

class Solution {
        public int solution(int N) {
            
            int A = 0;
            int B = N;
            int perimeter = 0;
            for (A = 1; A <= B; A++) {
                if (A * B == N){
                    perimeter = 2 * (A + B);
                    System.out.println("perimeter: " + perimeter);
                }
                if (N % (A+1) == 0) 
                    B = N/(A+1);
            }
            System.out.println("A: " + A);
            
            return perimeter;
        }
        
    }

Answer 1

设 l1 和 l2 为边长。考虑最小化|l1-l2|将使周长最小化。所以这将是一个解决方案：

public int solution(int n) {
    int sumMin =Integer.MAX_VALUE;
    for(int i=1 ;i<=Math.sqrt(n);i++) {
        if(n%i==0 ) {
            if(2*(i+n/i) < sumMin) sumMin=2*(i+n/i);    
        }   
    }   
    return sumMin;
}