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;
}
};
O(n ^ 1/2) Solution

Agree with @zx731 's comment. The code does not have to run a full loop of length
sqrt(area)
if it is running fromsqrt(area)
down to1
, which will return immediately if a match is found fori*(area/i) == area
. Because the loop is trying to get the largest matchingi
in range[1, n]
anyway.Consider the extreme case with
area = m*m
being a square number itself, wherem
is a huge integer. The following improved code will return from loop on the firsti
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 2line code is even longer?