3 line Clean and easy understand solution


  • 43
    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!

  • 0
    X

    Nice solution, golang implementation.

    func constructRectangle(area int) []int {
    	w := int(math.Sqrt(float64(area)))
    	for area%w != 0 {
    		w--
    	}
    	return []int{area / w, w}
    }
    

  • 0
    C

    Is it possible to have O(1) solution ?


  • 0

    @crazystonesss This is not likely to be true.

    A sub-problem of your request s to do primality test in O(1) time (since the answer for a prime input n is just w =1). However, the complexity of primality test is not found to be O(1).


Log in to reply
 

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