Problem

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:

  1. The area of the rectangular web page you designed must equal to the given target area.
  2. The width W should not be larger than the length L, which means L >= W.
  3. 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.

Examples

Example 1

1
2
3
4

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

1
2

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

Example 3

1
2

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

Constraints

  • 1 <= area <= 10^7

Solution

Method 1 – Integer Square Root and Factor Search

Intuition

To find the rectangle with area equal to the given value, and with the smallest difference between length and width, we should start from the square root of the area and search downwards for the largest factor. This ensures the length and width are as close as possible.

Approach

  1. Start with w = int(sqrt(area)), and decrement w until area % w == 0.
  2. Set l = area // w.
  3. Return [l, w].

Code

1
2
3
4
5
6
7
8

class Solution {
public:
    vector<int> constructRectangle(int area) {
        int w = sqrt(area);
        while (area % w != 0) --w;
        return {area / w, w};
    }
};
1
2
3
4
5

func ConstructRectangle(area int) []int {
    w := int(math.Sqrt(float64(area)))
    for area%w != 0 { w-- }
    return []int{area / w, w}
}
1
2
3
4
5
6
7

class Solution {
    public int[] constructRectangle(int area) {
        int w = (int)Math.sqrt(area);
        while (area % w != 0) w--;
        return new int[]{area / w, w};
    }
}
1
2
3
4
5
6
7

class Solution {
    fun constructRectangle(area: Int): IntArray {
        var w = Math.sqrt(area.toDouble()).toInt()
        while (area % w != 0) w--
        return intArrayOf(area / w, w)
    }
}
1
2
3
4
5
6

class Solution:
    def constructRectangle(self, area: int) -> list[int]:
        w = int(area ** 0.5)
        while area % w != 0:
            w -= 1
        return [area // w, w]
1
2
3
4
5
6
7

impl Solution {
    pub fn construct_rectangle(area: i32) -> Vec<i32> {
        let mut w = (area as f64).sqrt() as i32;
        while area % w != 0 { w -= 1; }
        vec![area / w, w]
    }
}
1
2
3
4
5
6
7

class Solution {
    constructRectangle(area: number): number[] {
        let w = Math.floor(Math.sqrt(area));
        while (area % w !== 0) w--;
        return [area / w, w];
    }
}

Complexity

  • ⏰ Time complexity: O(sqrt(area)), since we check at most sqrt(area) possible widths.
  • 🧺 Space complexity: O(1), only a few variables are used.