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.
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;
}
0 Comments