My AC O(logN), 8ms


  • 0
    F

    Based on binary search, and find "val", so that val * val>=x, while (val+1)*(val+1)>x.

    class Solution {
    public:
        int mySqrt(int x) {
            if(x <= 1)
                return x;
            int start = 1;
            int end = x - 1;
            while(true){
                int mid = (start + end) / 2;
                if(mid > x/mid){
                    end = mid - 1;
                    continue;
                }
                if((mid+1) < x/(mid+1)){
                    start = mid + 1;
                    continue;
                }
                if((mid+1) == x/(mid+1))
                    return mid+1;
                return mid;
            }
        }
    };

Log in to reply
 

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