Construct the Rectangle

🏠 ⬅️ ➡️

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.

Example 1:

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:

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

Example 3:

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

Constraints:

  • 1 <= area <= 107
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer :: area
    integer :: l, w

    area = 4
    call solve(area, l, w)
    write (*, '(A, I0, A, I0)') 'Length: ', l, '; Width: ', w

    area = 37
    call solve(area, l, w)
    write (*, '(A, I0, A, I0)') 'Length: ', l, '; Width: ', w

    area = 122122
    call solve(area, l, w)
    write (*, '(A, I0, A, I0)') 'Length: ', l, '; Width: ', w

contains

    subroutine solve(area, l, w)
        implicit none
        integer, intent(in) :: area
        integer, intent(out) :: l, w

        integer :: diff

        l = int(sqrt(real(area)))
        do while (l > 0)
            w = area / l
            if (w == 0) then
                exit
            end if
            diff = abs(l - w)
            if (diff == 0) then
                exit
            else if (diff < minval(diff, l-1, w-1)) then
                exit
            end if
            l = l - 1
        end do
    end subroutine solve

end program main
❌ Compiled
❌ Executed
❌ Correct 
! Declare variables
integer :: area, L, W

! Define main program
program main
    ! Read input
    read *, area

    ! Call function to solve problem
    call solve(area, L, W)

    ! Print output
    write (*,*) L, W
end program main

! Define function to solve problem
subroutine solve(area, L, W)
    ! Declare variables
    integer :: area, L, W

    ! Initialize variables
    L = 0
    W = 0

    ! Loop until we find the correct solution
    do while (L * W /= area .or. L < W)
        ! Increase length
        L = L + 1

        ! Check if width is too large
        if (L < W) then
            ! Reset width
            W = 0
        end if

        ! Check if width is too small
        if (L > W + 1) then
            ! Increase width
            W = W + 1
        end if
    end do
end subroutine solve
🌐 Data from online sources 
def constructRectangle(area: int) -> List[int]:
    width = int(area**0.5)
    while area % width != 0:
        width -= 1
    length = area // width
    return [length, width]

The algorithm starts by calculating the square root of the given area, using the sqrt function in each language. Since web pages with more rectangular shapes are preferred, we start the width from sqrt(area) and work our way down.

We initialize the variable width with the integer value of the square root of the area: width = sqrt(area). This initialization ensures that our width and length will be as close as possible to each other.

We then use a while loop to check if the current width divides the area evenly (area % width != 0). If it doesn't, we decrement the width by one and repeat the loop until we find a width that divides the area evenly.

Finally, we calculate the length by dividing the area with the width: length = area / width. We return the length and width as an array in the required sequence: [length, width].

🌐 Data from online sources 
#include <vector>
#include <cmath>

std::vector<int> constructRectangle(int area) {
    int width = std::sqrt(area);
    while(area % width != 0) {
        width -= 1;
    }
    int length = area / width;
    return {length, width};
}

The algorithm starts by calculating the square root of the given area, using the sqrt function in each language. Since web pages with more rectangular shapes are preferred, we start the width from sqrt(area) and work our way down.

We initialize the variable width with the integer value of the square root of the area: width = sqrt(area). This initialization ensures that our width and length will be as close as possible to each other.

We then use a while loop to check if the current width divides the area evenly (area % width != 0). If it doesn't, we decrement the width by one and repeat the loop until we find a width that divides the area evenly.

Finally, we calculate the length by dividing the area with the width: length = area / width. We return the length and width as an array in the required sequence: [length, width].