My 8ms C++ solution, simple to understand, with comments


  • 2
    L
    class Solution {
    public:
        int mySqrt(int x) {
            
            int p = 0, q = x;
            while(p < q)
            {
                // Basically, q = (p+q)/2. Code like below has two purpose: 
                // 1) avoid overflow.
                // 2) handle corner case, such as x = 1, prevent divided-by-zero error for p=x/q.
                q = max(1, p + (q - p) / 2);  
                p = x / q;
            }
            
            return p > q ?  q: p; // if the loop exits because p > q, return q; otherwise, p is the answer.
        }
    };

  • 0
    L

    Optimize a bit:

    class Solution {
    public:
        int mySqrt(int x) {
            
            if(x < 2) return x;
    
            int p = 0, q = x;
            while(p < q)
            {
                q = (p + q) / 2;  
                p = x / q;
            }
    
            return min(p, q);
        }
    };

Log in to reply
 

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