A web developer needs to know how to design a web page's size. So, given a specific rectangular web page’s area, your job by now is to design a rectangular web page, whose length L and width W satisfy the following requirements:
The area of the rectangular web page you designed must equal to the given target area.
The width W should not be larger than the length L, which means L >= W.
The difference between length L and width W should be as small as possible.
Return an array [L, W] where L and W are the length and width of the web page you designed in sequence.
Example 1:
Input: area = 4
Output: [2,2]
Explanation: The target area is 4, and all the possible ways to construct it are [1,4], [2,2], [4,1].
But according to requirement 2, [1,4] is illegal; according to requirement 3, [4,1] is not optimal compared to [2,2]. So the length L is 2, and the width W is 2.
Example 2:
Input: area = 37
Output: [37,1]
Example 3:
Input: area = 122122
Output: [427,286]
Constraints:
- 1 <= area <= 107
My Solution
We can solve this problem by taking the square root of area, and then just decrementing this number until it is divisible by area. Then we just put the larger factor in the first element of our output and the smaller factor in the second element of our output and return.
Time complexity is O(sqrt(area)) since in the worst case where area is prime, we will end up iterating sqrt(area) times to find the W. Space complexity is O(1) since we only require constant extra space.
class Solution {
public int[] constructRectangle(int area) {
int n = (int) Math.sqrt(area);
int[] out = new int[2];
while (area % n != 0) {
n--;
}
out[0] = area / n;
out[1] = n;
return out;
}
}