algoadvance

1. Construct the Rectangle

A web developer needs to know the dimensions of a rectangular web page that is targeted for advertisements. Given an area area, your task is to find out the dimensions length and width which satisfy the following:

1. The area of the rectangular web page you designed must equal to the given area.
2. The width width should not be larger than the length length, which means length >= width.
3. The difference between length and width should be as small as possible.

You need to return an array [length, width] being the dimensions of the rectangular web page you designed in that order.

Example

Input: area = 4
Output: [2, 2]

Input: area = 37
Output: [37, 1]

Input: area = 122122
Output: [427, 286]

Clarifying Questions

1. Is the area guaranteed to be a positive integer?
2. Could the area be very large, and should I be concerned about performance?
3. Is there a specific range for the area value?

Strategy

The problem can be solved efficiently by iterating from the square root of the area down to 1 to find the pair of factors (length, width) that yield the smallest difference and satisfy length >= width.

1. Start from the Square Root:
   • Begin iterating from int(sqrt(area)) down to 1 to find the possible width width such that area % width == 0.
   • For each valid width that divides the area evenly, compute the corresponding length as length = area // width.
2. Ensure Valid Dimensions:
   • Only keep the pair where length >= width.
   • Track the pair with the smallest difference length - width.
3. Return the optimal dimensions.

Code Implementation

from math import isqrt

def constructRectangle(area: int) -> list[int]:
    for width in range(isqrt(area), 0, -1):
        if area % width == 0:  # width is a valid factor
            length = area // width
            return [length, width]

# Example usage:
print(constructRectangle(4))       # Output: [2, 2]
print(constructRectangle(37))      # Output: [37, 1]
print(constructRectangle(122122))  # Output: [427, 286]

Time Complexity

• Time Complexity: O(sqrt(area)), because the loop runs from the integer square root of area down to 1.
• Space Complexity: O(1), because the space used does not scale with the input size.

This is an efficient approach for solving the problem as it minimizes the number of iterations by leveraging the properties of factors and the square root of the area.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?