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




Related Posts

Find Peak Element Problem

LeetCode 162. A peak element is an element that is...

Find Minimum In Rotated Sorted Array Problem

LeetCode 153. Suppose an array of length n sorted in...

Find Minimum In Rotated Sorted Array II Problem

LeetCode 154. Suppose an array of length n sorted in...

Search in Rotated Sorted Array II Problem

LeetCode 81. There is an integer array nums sorted in...

Search A 2D Matrix Problem

LeetCode 74. Write an efficient algorithm that searches for a...

Find First and Last Position of Element in Sorted Array Problem

LeetCode 34. Given the array nums after the possible rotation...