# O(n ^ 1/2) Solution

• ``````public:
vector<int> constructRectangle(int area) {
int n = (int) sqrt(area);
int j = 0;
for(int i=1; i <= n; ++i){
if(i*(area/i) == area) j = i;
}
vector<int> v{area/j,j};

return v;
}
};``````

• this can be faster if you start your loop from n to 1.

• Agree with @zx731 's comment. The code does not have to run a full loop of length `sqrt(area)` if it is running from `sqrt(area)` down to `1`, which will return immediately if a match is found for `i*(area/i) == area`. Because the loop is trying to get the largest matching `i` in range `[1, n]` anyway.

Consider the extreme case with `area = m*m` being a square number itself, where `m` is a huge integer. The following improved code will return from loop on the first `i` immediately.

``````    vector<int> constructRectangle(int area) {
for(int i=sqrt(area); i >= 1; --i)
if(i*(area/i) == area) return {area/i, i};
}
``````

• @zzg_zzm
Yes but it doesn't really matter, It would only add extra code making it longer

• @kevin36 Well, the difference is to find only the largest divisor v.s. all divisors of `A` in range `[1, sqrt(A)]`.

And you mean the 2-line code is even longer?

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