[LeetCode] 69. Sqrt(x)

Posted on | In

Problem

Implement int sqrt(int x).

Compute and return the square root of $x$, where $x$ is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

Example 1:

1
2
Input: 4
Output: 2

Example 2:

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

Explanation 1

  1. We can use binary search method to solve this problem. Left is 1, and right is the square root of the Integer.MAX_VALUE. mid is our guess number.

Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int mySqrt(int x) {
        if (x <= 1) return x;
        int left = 1;
        int right = x;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (mid == x / mid) {
                return mid;
            } else if (mid < x / mid) {
                if (mid+1 > x / (mid+1)) return mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1;
    }
}

Explanation 2

  1. Observe the square of the number: 1, 4, 9, 16, 25, 36, and observe their difference (add): 3, 5, 7, 9, 11. We notice that the difference is adding 2 each time. In other word, the value of add is plus 2 each time, and we can compare (sum += add with target), 1 + 3 = 4, 4 + 5 = 9, 9 + 7 = 16, 16 + 9 = 25, 25 + 11 = 36.

  2. So, we can initialize the sum = 0, add = 1, counter (or res) = 0, the next iteration, sum += add = 1, add = 3, counter = 1, in other word, when sum = 1, counter = 1, when sum = 4, counter = 2, and we compare the sum with target.

  3. Special case is the sum + add > MAX_VALUE so, we use MAX_VALUE - sum < add to avoid overflow.

Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int mySqrt(int x) {
        if (x <= 0) return 0;
        int add = 1;
        int sum = 0;
        int counter = 0;
        while (sum <= x) {
            if (Integer.MAX_VALUE - sum < add) return counter;
            sum += add;
            counter += 1;
            add += 2;
        }
        return counter-1;
    }
}