Construct the Rectangle Leetcode Solution

Difficulty Level Easy
algorithms coding Interview interviewprep LeetCode LeetCodeSolutions MathViews 3475

The problem Construct the Rectangle Leetcode Solution states that you are a web designer. And you are given a task to design a web page with some pre-defined area. There are some constraints imposed upon the design. The length of the web page needs to be greater or equal to the width of the web page, the area of the designed web page must be equal to the given area. Last but not the least, the difference between the length and width should be as small as possible. So, let’s take a look at a few examples before diving deep into solving the problem.

Construct the Rectangle Leetcode Solution

area = 4
[2,2]

Explanation: The length and width of the web page with an area equal to 4 can be either 1×4 or 2×2. But since we need to find the length and width such that they have a minimum difference between them. It’s better to choose 2×2 dimensions. The 2×2 dimension also follows that the length is greater or equal to the width of the page.

area = 23
[23, 1]

Explanation: You can have only two web pages with area = 23. you can either have dimensions 23×1 or 1×23. Since the web-page with dimensions 1×23 violates our first condition. We can have the web-page with size 23×1 only.

Approach for Construct the Rectangle Leetcode Solution

The problem Construct the Rectangle Leetcode Solution asks us to find out the suitable size of the web-page with some pre-defined area. The web-page dimensions should satisfy the imposed constraints. The three constraints are: length must be greater or equal to the width of the web-page, the area of the designed web-page must be equal to the given area, the difference between length and width must be minimum. We can easily find a set of dimensions that satisfy the given constraints by simply looping over the integers from 1 to the square root of the given area. We keep checking if the current integer divides the area. If it does, we check if the difference between its counterpart (the quotient received by dividing the given area by the current integer) have less difference than the current set. If all conditions are met, we update the answer.

Initially, we set the answer as areax1, since it always satisfies the given constraints. And in the solution, we try to find a better set that has a lesser difference between them. In the end, we return the dimensions as an array.

Code for Construct the Rectangle Leetcode Solution

C++ code

#include <bits/stdc++.h>
using namespace std;

vector<int> constructRectangle(int area) {
    vector<int> ans({area, 1});
    for(int i=1;i*i<=area;i++){
        if(area%i == 0 && (area/i - i)<(ans[0] - ans[1]))
            ans[0] = area/i, ans[1] = i;
    }
    return ans;
}

int main(){
    vector<int> ans = constructRectangle(4);
    cout<<ans[0]<<", "<<ans[1];
}

2, 2

Java Code

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
    public static int[] constructRectangle(int area) {
        int[] ans = {area, 1};
        for(int i=1;i*i<=area;i++){
            if(area%i == 0 && (area/i - i)<(ans[0] - ans[1])){
                ans[0] = area/i;
                ans[1] = i;
            }
        }
        return ans;
    }
    
  public static void main (String[] args) throws java.lang.Exception{
    int[] ans = constructRectangle(4);
    
    System.out.println(ans[0] + ", " + ans[1]);
  }
}
2, 2

Complexity Analysis

Time Complexity

O(sqrt(N)), where N is the area provided to the user. Since we have tried to find all the divisors of the given area until its square root, thus the time complexity is the square root of the input.

Space Complexity

O(1), since we have used only constant variables. The space complexity is also constant.

Translate »