Get started

Construct the Rectangle — Easy Problem & Solution

Design a rectangular page with a given area subject to three rules: the length L times the width W must equal area, L must be at least W, and the difference…

  • Difficulty: Easy
  • Topics: Math, Number Theory
  • Asked at: Amazon, TCS, Infosys
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Design a rectangular page with a given area subject to three rules: the length L times the width W must equal area, L must be at least W, and the difference L - W must be as small as possible.

Return [L, W].

Example 1

Input: area = 4
Output: [2,2]
Explanation: A square is the most balanced option.

Example 2

Input: area = 37
Output: [37,1]
Explanation: 37 is prime, so the only factorisation is 37 by 1.

Example 3

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

Constraints

  • 1 <= area <= 10000000

How to solve Construct the Rectangle

Factor pairs of area are symmetric about its square root: as W decreases below sqrt(area), the matching L grows. So the first divisor found walking down from floor(sqrt(area)) gives the smallest possible gap.

Approach

  1. Set W = floor(sqrt(area)).
  2. While area % W != 0, decrement W.
  3. Return [area / W, W].

Why it works

For any divisor d <= sqrt(area), the gap is area/d - d, which strictly decreases as d grows. The largest divisor at or below the square root therefore minimises the gap, and that is exactly what the downward walk finds first.

Complexity

  • Time — O(sqrt(area))
  • Space — O(1)

Pitfalls

  • Walking up from 1 finds the widest gap, not the narrowest.
  • Floating-point sqrt can land one off on a perfect square — a single guarded decrement or an explicit while (w * w > area) w-- fixes it.
  • The answer is [L, W] with L >= W, not the other way round.

Reference solution

Python

from typing import List

def constructRectangle(area: int) -> List[int]:
    w = int(area ** 0.5)
    while w * w > area:
        w -= 1
    while area % w != 0:
        w -= 1
    return [area // w, w]

JavaScript

var constructRectangle = function(area) {
    var w = Math.floor(Math.sqrt(area));
    while (w * w > area) w--;
    while (area % w !== 0) w--;
    return [area / w, w];
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 213 math problems · the whole catalogue