We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Construct the Rectangle

Number: 492

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given an integer representing the area of a rectangle, determine the dimensions (length L and width W) such that:

  1. The area equals the given value.
  2. The width W is not greater than the length L (i.e., L >= W).
  3. The difference between L and W is minimized.

Return the dimensions as an array [L, W].

Key Insights

  • The task is to find two factors of the area that are as close as possible.
  • Starting from the integer square root of the area ensures you get the closest factors.
  • Iterate downwards from the square root until a divisor is found.
  • Once the divisor (W) is determined, the corresponding length is simply area / W.

Space and Time Complexity

Time Complexity: O(sqrt(n)) where n is the area, since in worst case we iterate from sqrt(n) to 1. Space Complexity: O(1) as only a constant amount of extra space is used.

Solution

We solve the problem by iterating from the integer square root of the area downwards to find a divisor that evenly divides the area. This divisor is assigned to width W. The corresponding length L is computed using L = area / W. This guarantees that the difference L - W is minimized because the factors are as close together as possible. The approach leverages simple arithmetic and loops, ensuring clarity and efficiency.

Code Solutions

# Import the math module for square root calculation
import math

def constructRectangle(area):
    # Start with the integer square root of the area to get close factors
    for width in range(int(math.sqrt(area)), 0, -1):
        # If width divides area evenly, it is our optimal width
        if area % width == 0:
            length = area // width  # Calculate length
            return [length, width]  # Return dimensions as [L, W]
    return []  # Provided area is always >= 1, this line is never reached

# Example usage: print the result for area = 122122
print(constructRectangle(122122))
← Back to All Questions