3 line Clean and easy understand solution

• The W is always less than or equal to the square root of area
so we start searching at sqrt(area) till we find the result

``````public int[] constructRectangle(int area) {
int w = (int)Math.sqrt(area);
while (area%w!=0) w--;
return new int[]{area/w, w};
}
``````

• This post is deleted!

• This post is deleted!

• The upper bound `sqrt(N)` goes through the full loop if `area` is a prime number.

• talking about square root, what is the complexity. Maybe take use shift to get approximation;
1500 = 10111011100 (total 11bits/2 = 5, right shift 5, 101110), test from here to get SQRT, if (test * test < target) { while (test * test < target) test ++; test --;}

• I thought those two would run roughly the same time. Why are they so different?

``````public class Solution {
/*
// 103 ms
public int[] constructRectangle(int area) {
int sqrt = (int)Math.ceil(Math.sqrt(area));
while (area % sqrt != 0) sqrt++;
return new int[]{sqrt, area/sqrt};
}
*/
// 6 ms
public int[] constructRectangle(int area) {
int sqrt = (int)Math.sqrt(area);
while (area % sqrt != 0) sqrt--;
return new int[]{area/sqrt, sqrt};
}
}
``````

• I thought those two would run roughly the same time. Why are they so different?

Note that the `while` loop length is the major difference in your two solutions above: `O(N-sqrt(N))` vs `O(sqrt(N))`.

• `while (area % sqrt != 0) sqrt++;` vs `while (area % sqrt != 0) sqrt--;`.

The worst scenario is when `area` is a huge prime number. So you always want to loop over the shorter side `width` instead of the longer side `length`, where `width <= length`.

• @zzg_zzm Ahh, that makes sense. [1, sqrt] is definitely shorter than [sqrt, area]. thanks

• Thanks for the solution!

Here's a javascript implementation of it for reference.

``````var constructRectangle = function(area) {
let w = Math.floor(Math.sqrt(area));
while (area % w!==0) w--;

return [area/w, w];
};
``````

• Nice Solution :)

• Thanks. Your solution is much simpler than mine. Here is mine.

``````public class Solution {
public int[] constructRectangle(int area) {
double sqrt = Math.sqrt(area);
int int_sqrt = (int) sqrt;
if(int_sqrt * int_sqrt == area){
}else{
for(int i= int_sqrt; i >= 1; i--){
if(area % i == 0){
break;
}
}
}
}
}
``````

• Same idea! Thanks for sharing.

``````    public int[] constructRectangle(int area) {
for (int w = (int) Math.sqrt(area); w > 0; w--) {
if (area % w == 0) return new int[]{ area / w, w };
}
return new int[]{ 0, 0 };
}
``````

• @shawloatrchen oh,I forget that the number(satisfy the requests) closest to the square root of area is the best choice.thx,I get it!!!:)

• This post is deleted!

• Nice solution, golang implementation.

``````func constructRectangle(area int) []int {
w := int(math.Sqrt(float64(area)))
for area%w != 0 {
w--
}
return []int{area / w, w}
}
``````

• Is it possible to have O(1) solution ?

• @crazystonesss This is not likely to be true.

A sub-problem of your request s to do primality test in `O(1)` time (since the answer for a prime input `n` is just `w =1`). However, the complexity of primality test is not found to be `O(1)`.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.