Simple Java Solution, Beats 100%


  • 8
    public int[] constructRectangle(int area) {
            int[] result = new int[2];
            if(area == 0){
                return result;
            }
            int a = (int)Math.sqrt(area);
            while(area%a != 0){
                a--;
            }
            int b = area/a;
            result[0] = b;
            result[1] = a;
            return result;
        }

  • 0
    C

    it's a good solution,but why it cost 90ms or more when I increase the length (not decrease the width) ,does it make any difference?

    public static int[] constructRectangle(int area) {
            int[] result = new int[2];
            if(area == 0){
                return result;
            }
            int length = (int)(Math.ceil(Math.sqrt(area)));
            while(area%length != 0){
                length++;
            }
            int width = area/length;
            result[0] = length;
            result[1] = width;
            return result;
        }
    
    

  • 0
    Y

    @12063228 Because the power of two small number can yield a relatively large number. Taking a large prime number N as an example. Actually this is the worst case. The Math.sqrt(N) is far more less then N/2: sqrt(N) << N/2. (By solving the equation sqrt(N) = N/2 you can easily find out only when N is in [0, 4], sqrt(N) will large or equal to N/2). So if you increase the sqrt(N) to get the solution you need to step around N - sqrt(N) times. If you decrease it, the step you need is only around sqrt(N). Here we got: N - sqrt(N) = 2 * N/2 - sqrt(N) >> 2 * sqrt(N) - sqrt(N) = sqrt(N). So, decreasing the sqrt(N) takes less time.


  • 0
    C

    @YuleiLi thank you very much.got it!


  • 0
    G

    @prateek470 well,i notice what you mean,thx,I get it!!:)


  • 0
    S

    @prateek470 How do we ensure that the difference between the length and breadth pair is the lowest?


Log in to reply
 

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