3 line Clean and easy understand solution


  • 41
    S

    The W is always less than or equal to the square root of area
    so we start searching at sqrt(area) till we find the result

    public int[] constructRectangle(int area) {
            int w = (int)Math.sqrt(area);
    	while (area%w!=0) w--;
    	return new int[]{area/w, w};
    }
    

  • 0
    P
    This post is deleted!

  • 0
    F
    This post is deleted!

  • 0

    The upper bound sqrt(N) goes through the full loop if area is a prime number.


  • 0
    A

    talking about square root, what is the complexity. Maybe take use shift to get approximation;
    1500 = 10111011100 (total 11bits/2 = 5, right shift 5, 101110), test from here to get SQRT, if (test * test < target) { while (test * test < target) test ++; test --;}


  • 0
    Y

    I thought those two would run roughly the same time. Why are they so different?

    public class Solution {
        /*
        // 103 ms
        public int[] constructRectangle(int area) {
            int sqrt = (int)Math.ceil(Math.sqrt(area));
            while (area % sqrt != 0) sqrt++;
            return new int[]{sqrt, area/sqrt};
        }
        */
        // 6 ms
        public int[] constructRectangle(int area) {
            int sqrt = (int)Math.sqrt(area);
            while (area % sqrt != 0) sqrt--;
            return new int[]{area/sqrt, sqrt};
        }
    }
    

  • 6

    @ye23 said in 3 line Clean and easy understand solution:

    I thought those two would run roughly the same time. Why are they so different?

    Note that the while loop length is the major difference in your two solutions above: O(N-sqrt(N)) vs O(sqrt(N)).

    • while (area % sqrt != 0) sqrt++; vs while (area % sqrt != 0) sqrt--;.

    The worst scenario is when area is a huge prime number. So you always want to loop over the shorter side width instead of the longer side length, where width <= length.


  • 1
    Y

    @zzg_zzm Ahh, that makes sense. [1, sqrt] is definitely shorter than [sqrt, area]. thanks


  • 0
    D

    Thanks for the solution!

    Here's a javascript implementation of it for reference.

    var constructRectangle = function(area) {
        let w = Math.floor(Math.sqrt(area));
        while (area % w!==0) w--;
        
        return [area/w, w];
    };
    

  • 0
    I

    Nice Solution :)


  • 0
    F

    Thanks. Your solution is much simpler than mine. Here is mine.

    public class Solution {
        public int[] constructRectangle(int area) {
            double sqrt = Math.sqrt(area);
            int int_sqrt = (int) sqrt;
            int []answer = new int[2];
            if(int_sqrt * int_sqrt == area){
                answer[0] = int_sqrt;
                answer[1] = int_sqrt;
            }else{
                for(int i= int_sqrt; i >= 1; i--){
                    if(area % i == 0){
                        answer[0] = area / i;
                        answer[1] = i;
                        break;
                    }
                }
            }
            return answer;
        }
    }
    

  • 0

    Same idea! Thanks for sharing.

        public int[] constructRectangle(int area) {
            for (int w = (int) Math.sqrt(area); w > 0; w--) {
                if (area % w == 0) return new int[]{ area / w, w };
            }
            return new int[]{ 0, 0 };
        }
    

  • 0
    G

    @shawloatrchen oh,I forget that the number(satisfy the requests) closest to the square root of area is the best choice.thx,I get it!!!:)


  • 0
    G
    This post is deleted!

Log in to reply
 

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