Sqrt(area) intuitive solution in C++. Idea and Run-time explained.


  • 0
    W
        vector<int> constructRectangle(int area) {
          	/*
    	 The optimal case is when L = W and area = L*L. 
             Otherwise if L*W < area, then increase L, if L*W > area decrease W.
    	 Complexity is sqrt(area), because we might have to increase L at each step.
            */
            vector<int> d(2,int(sqrt(area)));
            while(true){
                int a = d[0]*d[1];
                if(a > area)
                    d[1]--;
                else if(a < area)
                    d[0]++;
                else
                    break;
            }
            return d;
        }
    

Log in to reply
 

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