requirements

As a Web developer, it is important to know how to size a page. Given a specific rectangular page area, your task is to design a page with length L and width W that meets the following requirements. Requirements:

1. You must design a rectangular page equal to the given target area. 2. Width W should not be greater than length L, in other words, L >= W. 3. The gap between length L and width W should be as small as possible.Copy the code

You need to output the length L and width W of your page in order.

Example:

Input: 4 output: [2,2] explanation: the target area is 4, all possible construction schemes are [1,4], [2,2], [4,1]. But according to requirement 2, [1,4] does not meet the requirements; According to requirement 3, [2,2] is better than [4,1]. So the output length L is 2 and the width W is 2.Copy the code

Description:

  • The given area is not greater than 10,000,000 and is a positive integer.
  • The length and width of your page must both be positive integers.

The core code

class Solution:
    def constructRectangle(self, area: int) - >List[int] :
        w = int(area ** 0.5)
        while True:
            if area % w == 0:
                return [area // w, w]
            else:
                w -= 1
Copy the code

This problem is a geometric optimization problem, there are three constraints: 1. 2. Length is not less than width; 3. The length and width are integers. The optimization objective of this problem is to find the rectangle with the minimum aspect ratio; If there is no restriction that both length and width are integers, then the optimal situation is that the area is the input area area of the square. We use the square of the length of the integer part as the initial value of rectangular width w, rectangular long integer is w can be divided exactly by area, the condition of the rectangular area/width/w, if not divisible, settle for second best, and will try again w minus 1, until the w can be divided exactly by area, each iteration will increase the aspect ratio, is straightforward.