My solution with O(log46340)


  • 0

    At first, I don't know how to deal with the int overflow. Then, I find out that, any input is assured to be less than 2,147,483,647. Thus, any output is assured to be less than 46340. Thus, we can simply set the high end as 46340 for a binary search. My code is as follows:

    public class Solution {
    public int sqrt(int x) {
        int low = 0, high = 46340; 
        int mid = 0;
        // previously, written as high = x. this is wrong!
        // it may cause integer overflow. because, x*x > 2,147,483,647. 
        // it will then be an arbitrary number!
        // why choose 46340 as the upper bound? 
        // INT_MAX = 2,147,483,647, sqrt(INT_MAX) = 46340.
        // because the input is assured to be less than or equal to 2,147,483,647.
        // thus, the result, is assured to be less than or equal to 46340.
    
        while(true)
        {
            mid = (low+high)/2;
            if(mid*mid == x)
                return mid;
            else if(mid*mid > x )
                high = mid;
            else// mid*mid < x;
                low = mid;
                
            if(low == high - 1)
            {
                if(high*high <= x)
                    return high;
                else if( low*low <=x)
                    return low;
            }
        }
    }
    

    I know this solution is not a good one. Besides, we need to calculate sqrt(INT_MAX) = 46340 first. Does anyone have a better solution?


  • 1
    M

    class Solution {
    public:
    int sqrt(int x) {

        int res = 0;
        int bit = 1 << 30;
        
        while (bit > x)
        {
            bit >>= 2;
        }
            
        while (bit != 0)
        {
            if (x >= res + bit) {
                    x -= res + bit;
                    res = (res >> 1) + bit;
            }
            else
            {
                res >>= 1;
            }
            bit >>= 2;
        }
        return res;
    }
    

    };


Log in to reply
 

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