8 lines concise and easy understand c++ solution binary search and Newton Iteration


  • 0
    A

    Binary search version:

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

    Newton Iteration:

    class Solution {
    public:
        int mySqrt(int x) {
            long res = x;
            while(res * res > x) res = (res + x / res)/2;
            return res;
        }
    };

Log in to reply
 

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