Leetcode Sqrt(x) Problem Solution

In this Leetcode Sqrt(x) Problem Solution Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.

You must not use any built-in exponent function or operator.

For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.

Leetcode Sqrt(x) Problem Solution


Problem solution in Python.

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        a = x ** 0.5
        # got this from
        # https://realpython.com/python-rounding/
        multiplier = 10 ** 0
        d = int(a * multiplier) / multiplier
        return int(d)

Problem solution in Java.

public int mySqrt(int x) {
        if(x==1) {
            return 1;
        }
        
        int e = x/2;
        int s = 0;
        int p =0 ;
        
        while(e>=s) {
            p = (e-s)/2 + s;
            if((long)p*p == (long)x) {
                return p;
            }
            else if((long)p*p < (long)x) {
                s = p+1;
            }
            else {
                e = p-1;
            }
        }
        
        return e;//return e because it is the closest full square within the range.
    }


Problem solution in C++.

int bs(long int start,long int end,long int target)
{
    if(startstart==target)
    return start;
    if(endend==target)
    return end;
    long int mid=(start+end)/2;
    if(midmid==target)
    return mid;
    if(midmid>target)
    {
        return bs(start,mid-1,target);
    }
    else
    { if((mid+1)*(mid+1)<=target)
    return bs(mid+1,end,target);
    return mid;
    }
    return mid;
}
class Solution {
public:
int mySqrt(int x) {
   long int start=1;
    long int end=x/2;
    long int target=x;
    long int ans=bs(1,x/2,x);
    return ans;
}
 
};


Problem solution in C.

int mySqrt(int x){
int a=sqrt(x);
return a;
}


Post a Comment

0 Comments