Construct the Rectangle - Practice Coding Problems

Construct the Rectangle - Problem

Math Easy

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:

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

Input & Output

Example 1 — Perfect Square Area

$ Input: area = 4

› Output: [2,2]

💡 Note: Area 4 can form a 2×2 square, which has the minimum possible difference of 0

Example 2 — Non-Square Area

$ Input: area = 6

› Output: [3,2]

💡 Note: Area 6 has factors: 1×6 (diff=5) and 2×3 (diff=1). The 3×2 rectangle has minimum difference

Example 3 — Prime Number Area

$ Input: area = 7

› Output: [7,1]

💡 Note: Area 7 is prime, so only possible rectangle is 7×1

Constraints

1 ≤ area ≤ 10⁷

Visualization

Tap to expand

Understanding the Visualization

Input

Given area = 12

Process

Find factors closest to square

Output

Return [4, 3] rectangle

Key Takeaway

🎯 Key Insight: Start from the square root and work backwards to find the largest valid width ≤ √area

Asked in

G Google 15 a Amazon 12

Brief HTML summary: The key insight is that the optimal rectangle is closest to a square. Best approach starts from √area and works backwards: Time: O(√n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized - Square Root Approach	O(√n)	O(1)	Start from square root and work backwards to find optimal width
Brute Force - Linear Search	O(n)	O(1)	Check every possible width from 1 to area

Optimized - Square Root Approach — Algorithm Steps

Calculate square root of area
Start from floor(sqrt(area)) and decrement
Find first width that divides area evenly
Return [area/width, width]

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate

Find sqrt(12) = 3.46, so start with w=3

Check

Test if 12 % 3 == 0 (yes!)

Found

L = 12/3 = 4, return [4,3]

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void solution(int area, int* result) {
    int w = (int) sqrt(area);
    while (w > 0) {
        if (area % w == 0) {
            int l = area / w;
            result[0] = l;
            result[1] = w;
            return;
        }
        w--;
    }
    result[0] = area;
    result[1] = 1;
}

int main() {
    int area;
    scanf("%d", &area);
    
    int result[2];
    solution(area, result);
    
    printf("[%d,%d]\n", result[0], result[1]);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(√n)

At most iterate from sqrt(area) down to 1, but usually finds answer quickly

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

23.0K Views

Medium Frequency

~15 min Avg. Time

680 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized - Square Root Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler