# Solution For Sqrtx

The problem statement for the Sqrtx problem on LeetCode is as follows:

Given a non-negative integer x, compute and return the square root of x.

Since the output has to be an integer, we need to use integer division instead of floating-point division while calculating the square root of x.

Approach:

One way to approach this problem is to perform a binary search on the possible integer values (0 to x) to determine the integer value which when squared is closest to x.

Algorithm:

1. Define a variable ‘left’ as 0, and another variable ‘right’ as x.
2. While left is less than or equal to right, perform the following steps:
a. Define a variable ‘mid’ as the integer division of the sum of left and right by 2.
b. Calculate the square of mid as ‘square_mid’.
c. Compare square_mid with x and perform the following:
i. If square_mid is less than x, make left equal to mid + 1.
ii. If square_mid is greater than x, make right equal to mid – 1.
iii. If square_mid is equal to x, return mid as the square root of x.
3. If x is 0, return 0 as the square root of 0.
4. If x is 1, return 1 as the square root of 1.
5. If the square root of x is not an integer, return the integer part of the square root of x.

Code:

Here is the Python code for the above algorithm:

`class Solution: def mySqrt(self, x: int) -> int: if x == 0: return 0 if x == 1: return 1 left, right = 0, x while left <= right: mid = (left+right)//2 if mid*mid == x: return mid elif mid*mid < x: left = mid + 1 else: right = mid - 1 return right`

Time Complexity: O(log n) where n is the given number, as we are performing a binary search.

Space Complexity: O(1) as we are not using any extra space.

Note: The code above has been minimally edited from the original to ensure that it is in line with our guidelines.

## Step by Step Implementation For Sqrtx

```class Solution {
public int mySqrt(int x) {
if (x == 0) return 0;
int left = 1, right = x;
while (true) {
int mid = left + (right - left)/2;
if (mid > x/mid) {
right = mid - 1;
} else {
if (mid + 1 > x/(mid + 1))
return mid;
left = mid + 1;
}
}
}
}```
```class Solution:
def mySqrt(self, x: int) -> int:

if x == 0:
return 0

left = 1
right = x

while left <= right:
mid = left + (right - left) // 2

if mid > x / mid:
right = mid - 1
else:
left = mid + 1

return right```
```var mySqrt = function(x) {

//edge case
if (x == 0) return 0;

//initiate left and right pointers
let left = 1, right = x;

//perform binary search
while (left <= right) {
//calculate middle
let middle = Math.floor((left + right) / 2);

//if x is a perfect square, return middle
if (middle * middle == x) {
return middle;
}
//if x is less than the square of middle, move the right pointer to the left
else if (x < middle * middle) {
right = middle - 1;
}
//if x is greater than the square of middle, move the left pointer to the right
else {
left = middle + 1;
}
}

//after the while loop terminates, left will be greater than right
//therefore, left - 1 will be the greatest integer less than the square root of x
return left - 1;
};```
```class Solution {
public:
int mySqrt(int x) {
if (x == 0) return 0;
int left = 1, right = x;
while (true) {
int mid = left + (right - left)/2;
if (mid > x/mid) {
right = mid - 1;
} else {
if (mid + 1 > x/(mid + 1))
return mid;
left = mid + 1;
}
}
}
};```
```public class Solution {
public int MySqrt(int x) {
// Newton's method
// Time complexity: O(logx)
// Space complexity: O(1)

long r = x;
while (r * r > x) {
r = (r + x / r) / 2;
}
return (int) r;
}
}```

## Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]