Regular O(n) and O(logn) binary approaches


  • 0
    L

    The regular one is fairly straight-forward. Go as close as possible and return a number <= the sq root.

    public int mySqrt_slow(int x) {
            if(x<=1) {
                return x;
            }
            
            long res = 0;
            int max = Integer.MIN_VALUE;
            while(res<=x/2) {
                if(res*res>(long)x) {
                    break;
                }            
                max = Math.max((int)res,max);            
                res++;
            }
            return max;
        }
    

    Alternative is to use a binary search. Use long to avoid overflows. The idea is to pick a number that is half of the previous. If nothing works, return the last high.

        public int mySqrt(int x) {
            if(x<=1) {
                return x;
            }
            int l = 1;
            int h = x/2;
            while(l<=h) {
                int p = (h-l)/2+l;            
                if((long)p*p==(long)x) {
                    return p;
                }
                else if((long)p*p>(long)x) {
                    h=p-1;
                }
                else {
                    l=p+1;
                }
            }
            return h;
        }
        
        
        
    

Log in to reply
 

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