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;
}