Using binary search accepted, but one question


  • 15
    Y
    int sqrt(int x) {
            if(x == 0 || x == 1){
                return x;
            }
            int l = 1, r = x, res;
            while(l <= r){
                int m = (l + r)/2;
                if(m == x / m){ 
                    return m;
                }else if(m > x / m){
                    r = m - 1;
                }else{
                    l = m + 1;
                    res = m;
                }
            }
            return res;
        }
    

    My question is:
    If using if(m * m == x) instead of if(m == x / m) (and if(m * m > x) instead of if(m > x / m) ), I will get "Time Limit Exceeded" on case 2147395599. Why that happens?

    Thank you in advance!


  • 30
    B

    If (m * m) overflows the 32 bit int limit, you might end up with an infinite loop.


  • 0
    Y

    Oh you are right, thanks!


  • 0
    C

    This can be solved with a less r ,such as :
    r =(int)Math.pow(Math.pow(2,31)-1,0.5)


  • 1
    M

    It's not the point. If you use Math.pow, why not use Math.sqrt ? It's no the answer to use the Math class, and you should give an answer without Math class.


  • 0
    N

    I do not quite understand.If overflows, end the loop, then what to be returned?


  • 2
    X

    When (m * m) overflows, the search range is still cut by half if no return, even through the wrong half may be cut. So, the infinite loop is not caused by overflow of (m * m), at least directly. It is instead caused by overflow of indices, i.e., l, r, m. See the example below: (m * m) still overflows, but no infinite loop, just yields wrong answer.

    In summary, overflow of (m * m) causes overflow of indices, thus cause infinite loop indirectly. In this sense, the accepted answer is at best incomplete, if not misleading.

    I post my multiplication- and division-based implementations in case they may be of help.

    class Solution {
    public:
        int sqrt(int x) {
            if(x == 0 || x == 1){
                return x;
            }
            long l = 1, r = x, res;
            while(l <= r){
                long mid = (l + r)/2;
                int m = mid;
                if(m * m == x){ 
                    return mid;
                }else if(m * m > x){
                    r = mid - 1;
                }else{
                    l = mid + 1;
                    res = mid;
                }
            }
            return res;
        }
    };
    

Log in to reply
 

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