O(n ^ 1/2) Solution


  • 0
    K
    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;
        }
    };

  • 0
    Z

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


  • 0

    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};
        }
    

  • 0
    K

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


  • 1

    @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?


Log in to reply
 

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