Construct the Rectangle
Problem
Given the area of a rectangle, return [L, W] (L ≥ W) such that L × W = area, the absolute difference L − W is minimised, and the pair is as close to a square as possible.
area = 122122[427, 286]import math
def construct_rectangle(area):
w = int(math.isqrt(area))
while area % w != 0:
w -= 1
return [area // w, w]function constructRectangle(area) {
let w = Math.floor(Math.sqrt(area));
while (area % w !== 0) w--;
return [area / w, w];
}class Solution {
public int[] constructRectangle(int area) {
int w = (int)Math.sqrt(area);
while (area % w != 0) w--;
return new int[]{ area / w, w };
}
}vector<int> constructRectangle(int area) {
int w = (int)sqrt((double)area);
while (area % w != 0) w--;
return { area / w, w };
}Explanation
We want a rectangle with the given area whose sides are as close to a square as possible. The closest pair always has its width near sqrt(area), so that is where we start looking.
We set w = floor(sqrt(area)) and step it down by one until w evenly divides the area. The first such w gives the widest valid width that does not exceed the square root.
Because w is the largest divisor at or below sqrt(area), its partner L = area / w is the smallest divisor at or above the square root. That pairing makes L - W as small as possible.
We return [area / w, w] with the longer side first.
Example: area = 36. floor(sqrt(36)) = 6, and 36 % 6 == 0 immediately, so W = 6 and L = 6 — a perfect square. For area = 122122, walking down from sqrt lands on W = 286, giving [427, 286].