O(logN) Bisection method


  • 14
    bool isPerfectSquare(int num) {
        long long l = 0, r = num;
        while (l <= r) {
            long long mid = (l + r) >> 1;
            long long sqmid = mid * mid;
            if (sqmid > num) r = mid - 1;
            else if (sqmid < num) l = mid + 1;
            else return true;
        }
        return false;
    }

  • 5
    B

    I have a very similar answer. One trick, instead of using long long to prevent overflow, you can check to see if mid * mid == target => mid == target / mid, which won't overflow.


  • 2

    mid == target / mid and meanwhile target % mid == 0.
    thank you~


  • 9
    N
    public boolean isPerfectSquare(int num){
            
            if(num <= 0) return false;
            
            int left = 1, right = num;
            
            while(left <= right){
                int mid = left + (right - left)/2;
                //用除法可以避免溢出
                if(mid > num / mid){
                    right = mid - 1;
                }else if(mid < num / mid){
                    left = mid + 1;
                }else{
                    return num % mid == 0;
                }
            }
            return false;
        }
    

  • 0
    R

    Golang solution:

    func isPerfectSquare(num int) bool {
        if num == 1 {
                return true
        }
        l := 1
        r := num
        for l < r {
            mid:= l + (r - l) / 2
            a := int(math.Pow(float64(mid), 2))
            if a == num {
                return true
            } else if a < num {
                l = mid + 1
            } else {
                r = mid - 1
            }
        }
        return int(math.Pow(float64(l), 2)) == num
    }
    

  • 0
    F

    @noobsky If you set the initialized maxValue to (int)Math.sqrt(Integer.MAX_VALUE),you will not get overflow problem because (int)Math.sqrt(Integer.MAX_VALUE) * (int)Math.sqrt(Integer.MAX_VALUE) must less than or equal Integer.MAX_VALUE.To core code,using this method will not violate the regulations of this work.


  • 0
    F

    @noobsky You are a chinese,me too,haha.


  • 0
    A

    @ShuangquanLi why target%mid==0 and how long long solve this problem?


Log in to reply
 

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