Leetcode 0492 Construct the Rectangle

Problem statement

https://leetcode.com/problems/construct-the-rectangle/

Solution

We need to find the biggest divisor of number n, which is not more than $\sqrt{n}$. So, just start from $d = \sqrt{n}$ and decrease $d$, until $n$ can be divided by $d$.

Complexity

Time complexity is O(sqrt{n}), space complexity is O(1).

Code

class Solution:
    def constructRectangle(self, area):
        for i in range(int(sqrt(area)), 0, -1):
            if area % i == 0:
                return [area//i, i]