O(log X) using binary search

  • 1

    Since x^2 is a monotonically increasing sequence, we can apply binary search.

    typedef long long ll;
    class Solution {
        int sqrt(int x) {
            int lo=0,hi=1<<(sizeof(int) * 4);
                int mid=lo+(hi-lo)/2;
                ll mid2=(ll)mid*mid;
                if(mid2<x) lo=mid+1;
                else if(mid2>x) hi=mid-1;
                else return mid;
            return (ll)lo*lo>x?lo-1:lo;

Log in to reply

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