# Sqrt(x) Problem

## Description

LeetCode Problem 69. 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.

Example:

1
2
3

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

## Solution

#### Binary Search Approach

A simple `brute force`

approach is to enumerate all possible solutions from 1 to *x/2*, and check which one is the square root of *x*. The time complexity of this approach is O(n).

We can use `binary search`

to speed up the search for the square root. We set two pointers *l* and *r*. The left pointer *l* starts from 0, and the right pointer *r* starts from x. During each iteration, we calculate *m* to be the average of *l* and *r* (*m = (l + r) / 2*). If *m * m* equals *x*, we find the square root. We can stop the search and return *m*. If *m * m* is larger than *x*, it means the right range *r* is too big. We can set *r* to be *m - 1* and keep on searching. If *m * m* is smaller than *x*, it means the left range *l* is too small. We can set *l* to be *m + 1* and keep on searching. We abort the search until *l* is greater than *r*.

As we need to find the square root that is the largest integer whose square is less than *x*, we use a variable *pos* to track this. Every time we are in the condition that *m * m* is less than *x*, it is possible that this *m* is the final answer, so we use *pos* to remember this *m*. When the binary search is finished, we return *pos*.

Here is a walk-through of the approach to find the square root of x = 45.

1
2
3
4
5
6
7
8

iteration | l | r | m | pos
0 0 45 22 - <-- m*m = 484 > 45, set r = m-1 = 21
1 0 21 10 - <-- m*m = 100 > 45, set r = m-1 = 9
2 0 9 4 4 <-- m*m = 16 < 45, set l = m+1 = 5
3 5 9 7 4 <-- m*m = 49 > 45, set r = m-1 = 6
4 5 6 5 5 <-- m*m = 25 < 45, set l = m+1 = 6
5 6 6 6 6 <-- m*m = 36 < 45, set l = m+1 = 7
6 7 6 6 6 <-- l > r, break, the square root is pos = 6.

The time complexity of the binary search approach is O(logn), and the space complexity is O(1).

## Sample C++ Code

This is a C++ implementation of the binary search approach.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include <iostream>
#include <algorithm>
using namespace std;
int mySqrt(int x) {
long long l, m, r, pos;
l = 0, r = x;
while (l <= r) {
m = (l + r) / 2;
long long s = m*m;
if (s == x)
return m;
if (s < x) {
l = m + 1;
pos = m;
} else {
r = m - 1;
}
}
return pos;
}
int main() {
cout << mySqrt(45) << endl;
}