### Problem statement

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

Since the return type is an integer, the decimal digits are **truncated**,

and only **the integer part** of the result is returned.

**Note**: You are not allowed to use any built-in exponent function or operator, such as

`pow(x, 0.5)`

or `x ** 0.5`

.

Problem statement taken from: https://leetcode.com/problems/sqrtx

**Example 1:**

```
Input: x = 4
Output: 2
```

**Example 2:**

```
Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.
```

**Constraints:**

```
0 <= x <= 2^31 - 1
```

### Explanation

#### Brute force

The simple approach to this problem is to try with all-natural numbers starting from 1.

We continue increasing the number till the square of the number is greater than **x**.

C++ snippet of the above approach will look like this:

```
int i = 1, result = 1;
while (result <= x)
{
i++;
result = i * i;
}
return i - 1;
```

The time complexity of the above approach is **O(√ n)**, since we are running

a loop from 1 till the square root of that number.

The algorithm can still be improved by using the binary search concept here.

#### Binary search

Since the value of **i*i** i.e., square of numbers increasing monotonically,

we can use this concept to find the square root of the number using

binary search.

Let's check the algorithm below:

```
- return x if x <= 1
- initialize start = 2, end = x, middle = 0
- Loop while start <= end
- middle = start + ( end - start )/ 2
- if middle == x / middle
- return middle
- if middle < x / middle
- set start = middle + 1
- else
- set end = middle - 1
- if start > x /start
- return start - 1
- return start
```

The time complexity of the above approach is **O(log(n))**

##### C++ solution

```
class Solution {
public:
int mySqrt(int x) {
if(x <= 1){
return x;
}
int start = 2, end = x, middle;
while(start <= end){
middle = start + (end - start)/2;
if(middle == x/middle){
return middle;
}
if(middle < x/middle){
start = middle + 1;
} else {
end = middle - 1;
}
}
if(start > x/start){
return start - 1;
}
return start;
}
};
```

##### Golang solution

```
func mySqrt(x int) int {
start := 0
end := x
for start <= end {
middle := start + ( end - start )/2
if middle * middle > x {
end = middle - 1
} else if (middle + 1)*( middle + 1) > x {
return middle
} else {
start = middle + 1
}
}
return start
}
```

##### Javascript solution

```
var mySqrt = function(x) {
let start = 0, end = x, middle = 0;
while (start < end) {
middle = parseInt((start + end)/2);
if (middle * middle === x) {
return middle;
}
if (x < middle * middle) {
end = middle - 1;
} else {
start = middle + 1;
}
}
return x < end * end ? end - 1 : end;
};
```

Let's dry-run our algorithm to see how the solution works.

```
x = 8
Step 1: x <= 1
8 <= 1
false
Step 2: start = 2
end = 8
Step 3: Loop while 2 <= 8
true
middle = 2 + (8 - 2) / 2
= 2 + 6 / 2
= 2 + 3
= 5
middle == x / middle
5 == 8 / 5
5 == 1
false
middle < x/middle
5 < 8 / 5
5 < 1
false
end = middle - 1
end = 5 - 1
end = 4
Step 4: Loop while 2 <= 4
true
middle = 2 + (4 - 2) / 2
= 2 + 2 / 2
= 2 + 1
= 3
middle == x / middle
3 == 8 / 3
3 == 2
false
middle < x/middle
3 < 8 / 3
3 < 2
false
end = middle - 1
end = 3 - 1
end = 2
Step 4: Loop while 2 <= 2
true
middle = 2 + (2 - 2) / 2
= 2 + 0 / 2
= 2 + 0
= 2
middle == x / middle
2 == 8 / 2
2 == 4
false
middle < x/middle
2 < 8 / 2
2 < 4
true
start = middle + 1
start = 2 + 1
start = 3
Step 5: Loop while 3 <= 2
false
Step 6: if start > x/start
3 > 8 / 3
3 > 2
return start - 1
So the answer is 2.
```

## Top comments (0)