492. Construct the Rectangle
Model: qwen2.5-coder:14b
Topics:
FAANG asked: 0
Acceptance rate: 50.6%
Problem Breakdown
The problem requires designing a rectangular web page with a given area such that the length ( L ) is greater than or equal to the width ( W ), and the difference between ( L ) and ( W ) is minimized. The inputs are:
- An integer
arearepresenting the area of the rectangle.
The outputs are:
- A list
[L, W]where ( L ) is the length and ( W ) is the width of the rectangle.
Implicit constraints include:
- ( 1 \leq \text{area} \leq 10^7 )
- The width ( W ) should not be larger than the length ( L ).
- The difference between ( L ) and ( W ) should be minimized.
Edge cases to consider:
- When the area is a perfect square, e.g.,
area = 4, where both dimensions are equal. - When the area is a prime number, e.g.,
area = 37, where one dimension will be 1 and the other will be the area itself.
Intuition
A brute-force approach would involve iterating from 1 to the square root of the area to find pairs ((L, W)) such that ( L \times W = \text{area} ). However, this approach is inefficient because it checks all possible pairs up to the square root, leading to a time complexity of ( O(\sqrt{\text{area}}) ).
The key insight is to start from the largest possible width (which is the integer part of the square root of the area) and move downwards. This ensures that the first valid pair found will have the smallest difference between ( L ) and ( W ), as we are moving from the closest dimensions to the farthest.
Approach
- Calculate the integer part of the square root of the area, which serves as the starting point for width ( W ).
- Iterate downwards from this value until a pair ((L, W)) is found such that ( L \times W = \text{area} ).
- Return the first valid pair found.
The algorithm uses a simple loop to find the dimensions, ensuring that the difference between ( L ) and ( W ) is minimized by starting from the largest possible width.
Complexity Analysis
- Time Complexity: ( O(\sqrt{\text{area}}) ). This is because we iterate from the square root of the area downwards.
- Space Complexity: ( O(1) ). We only use a constant amount of extra space for variables.
Solution
import math
def constructRectangle(area: int) -> List[int]:
# Start with the largest possible width, which is the integer part of the square root of the area
w = int(math.sqrt(area))
# Iterate downwards to find the first valid pair (L, W)
while True:
if area % w == 0:
return [area // w, w]
w -= 1
# Example usage:
# constructRectangle(4) returns [2, 2]
# constructRectangle(37) returns [37, 1]
# constructRectangle(122122) returns [427, 286]
Edge Cases Handled
- Perfect Square: When the area is a perfect square (e.g.,
area = 4), the loop will find ( W = L ). - Prime Number: When the area is a prime number (e.g.,
area = 37), the loop will eventually find ( W = 1 ) and ( L = \text{area} ). - General Case: For any other area, the algorithm ensures that the difference between ( L ) and ( W ) is minimized by starting from the largest possible width.