In the 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.
Example 1:
Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.
Example 2:
Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842…, and since we round it down to the nearest integer, 2 is returned.
Constraints:
- 0 <= x <= 231 – 1
Solution in C Programming
int mySqrt(int x){
unsigned int i=1;
unsigned int res=0;
while(i*i<=x)
{
res++;
i++;
}
return res;
}Solution in C++ Programming
class Solution {
public:
int mySqrt(int A) {
int res = A;
long long low = 1, high = A;
while(low <= high) {
long long mid = (low + high)/2;
if(mid * mid == A) return mid;
else if(mid * mid < A) {
res = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return res;
}
};Solution in Java Programming
class Solution {
public int mySqrt(int x) {
if(x == 0) return 0;
int left = 1, right= x;
while(left <= right){
int mid = left + (right - left)/2;
if(mid == x/mid){
return mid;
}else if(mid> x/mid){
right = mid -1;;
}else{
left = mid +1;
}
}
return right;
}
}Solution in Python Programming
class Solution(object):
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
if x==0:
return 0
for i in range(1,x+1):
n = i*i
if n==x:
return i
elif n>x:
return i-1
else:
continueSolution in C# Programming
public class Solution {
public int MySqrt(int x) {
if(x==0)return 0;
if(x==1)return 1;
int left = 0;
int right = x/2;
while(left <= right)
{
int mid = left + (right - left) / 2;
long numb = (long) mid * mid;
if(numb == x) return mid;
if(numb > x)
{
right = mid - 1;
}
else
{
left = mid + 1;
}
}
return right;
}
}Also read,