Construct the Rectangle trong C++

Cho diện tích S, tìm kích thước hình chữ nhật L × W (L ≥ W) thỏa mãn L × W = S và |L - W| nhỏ nhất.

Ví dụ: S = 4 → [2,2] (các cặp: [1,4], [2,2], [4,1]; [2,2] tối ưu).

Giải thuật

Duyệt i từ √S xuống 1, i đầu tiên chia hết S sẽ cho W = i, L = S/i (đảm bảo L ≥ W và hiệu nhỏ nhất).

Ví dụ triển khai C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<int> constructRectangle(int area) {
        for (int i = sqrt(area); i >= 1; --i) {
            if (area % i == 0)
                return {area / i, i};
        }
        return {-1, -1};
    }
};

void print(vector<int> v) {
    cout << "[" << v[0] << ", " << v[1] << "]" << endl;
}

int main() {
    Solution ob;
    print(ob.constructRectangle(4)); // [2, 2]
    return 0;
}

Đầu vào / Đầu ra

Input: 4
Output: [2, 2]