algoadvance

Leetcode 492. Construct the Rectangle

Problem Statement:

The problem is to find a pair of integers (L, W) such that:

  1. L * W = area
  2. L >= W
  3. The difference between L and W is minimal.

Given an integer area, you need to output the pair (L, W).

Clarifying Questions:

  1. Q: What is the range of the area?
    • A: The area is a positive integer and typically within the constraint limits of the problem (1 <= area <= 10^7).
  2. Q: Can the values of L and W be equal?
    • A: Yes, L can be equal to W (especially in case of perfect squares).
  3. Q: Should I consider both L and W to be integers?
    • A: Yes, L and W should be integers.

Strategy:

To solve this problem:

  1. Start from the square root:
    • Since we want L and W to be as close as possible, start checking from the square root of area. This approach ensures that the values of L and W are close.
  2. Iterate Downwards:
    • Iterate downwards from the square root until you find a W that divides the area perfectly.
  3. Compute L:
    • For each valid W, compute L as area / W.
  4. Return the L and W Pair:
    • When the first pair is found, return (L, W) where L is always equal to or greater than W.

Time Complexity:

Code:

public class ConstructRectangle {
    public int[] constructRectangle(int area) {
        // Start from the square root of the area
        int W = (int) Math.sqrt(area);
        
        // Iterate downwards to find the width that divides the area perfectly
        while (area % W != 0) {
            W--;
        }
        
        // Compute L and return the results
        int L = area / W;
        return new int[] {L, W};
    }
    
    public static void main(String[] args) {
        ConstructRectangle cr = new ConstructRectangle();
        // Example usage:
        int[] result = cr.constructRectangle(122122);
        System.out.println("L = " + result[0] + ", W = " + result[1]);
    }
}

Explanation:

  1. Initial Step: Compute the integer value of square root of area.

  2. Iterate: Check each value from this square root downwards to 1.
    • If a value perfectly divides the area (area % W == 0), then it can be considered as W.

  3. Calculate L: Divide area by W to get L.

  4. Output: Return the pair (L, W).

This method ensures that the pair (L, W) you find is the closest possible dimensions that could form the given area.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI