492 Construct the Rectangle

1. Description

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.

 

constraints :

• 1 <= area <= \(10^{7}\)

2. Algorithms

When we consider prime factor of input area, the smallest difference between L and W became sqrt of area if area is same with L multiply W. So when we iterate integers to find proper L and W under power of current value is smaller than area.

 

1. Start
2. Declare two variable L, W. Initialize them to area and 1.
3. Declare variable i which initial value is 1.
4. Repeat the steps until power of i is bigger than area.
   
   1. If remainder of area divide i is zero, update W as i and L as area // i.
   2. Increment i by 1.
5. If W is bigger than L when the loop ends, change value of them.
6. Return result in format [L, W].
7. End

3. Codes

class Solution:
    def constructRectangle(self, area: int) -> List[int]:
        # L : bigger value fits L * W = area
        # W : smaller value fits L * W = area 
        # i : index iterating through ` to area under conditions (i * i <= area)
        L, W, i = area, 1, 1 
        
        while i * i <= area : 
            if area % i == 0 : 
                L = area // i
                W = i 
            i += 1
            
        if W > L : 
            L, W = W, L 
        return [L, W]

4. Conclusion