Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/492.html

492. Construct the Rectangle

Level

Easy

Description

For a web developer, it is very important to know how to design a web page’s size. So, given a specific rectangular web pages 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.

You need to output the length L and the width W of the web page you designed in sequence.

Example:

Input: 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.

Note:

  1. The given area won’t exceed 10,000,000 and is a positive integer.
  2. The web page’s width and length you designed must be positive integers.

Solution

Since the width is less than or equal to the length, the width is at most the square root of the target area. Also, the width is at least 1. The object is to find the greatest width such that the target area is divisible by the width.

After the greatest width is found, the length can be obtained as well. Return the length and the width as an array.

  • class Solution {
    public int[] constructRectangle(int area) {
        int sqrt = (int) Math.sqrt(area);
        int width = sqrt;
        while (width > 1) {
            if (area % width == 0)
                break;
            width--;
        }
        int length = area / width;
        int[] rectangle = {length, width};
        return rectangle;
    }
}

  • class Solution:
    def constructRectangle(self, area: int) -> List[int]:
        w = int(sqrt(area))
        while area % w != 0:
            w -= 1
        return [area // w, w]

############

class Solution(object):
  def constructRectangle(self, area):
    """
    :type area: int
    :rtype: List[int]
    """
    root = int(area ** 0.5)
    while root > 0:
      if area % root == 0:
        return int(area / root), root
      root -= 1


  • class Solution {
public:
    vector<int> constructRectangle(int area) {
        int w = sqrt(1.0 * area);
        while (area % w != 0) --w;
        return {area / w, w};
    }
};

  • func constructRectangle(area int) []int {
	w := int(math.Sqrt(float64(area)))
	for area%w != 0 {
		w--
	}
	return []int{area / w, w}
}

All Problems

All Solutions