Problem Description

The Sqrt(x) problem asks you to compute and return the integer square root of a non-negative integer x. Specifically, you need to find the greatest integer r such that r * r <= x. The result should be an integer (rounded down if x is not a perfect square).

• Input: A non-negative integer x.
• Output: The integer part of the square root of x.
• Constraints:
  • 0 ≤ x ≤ 2³¹ - 1
  • Only one valid answer exists for each input.
• Note: Do not use any built-in exponent or square root functions.

Thought Process

The most straightforward way to solve this problem is to check every integer starting from 0 and see if its square is less than or equal to x. However, this approach is inefficient for large values of x.

To optimize, we notice that the square root function is monotonically increasing: as the input increases, so does the output. This property allows us to use binary search to find the integer square root efficiently.

Binary search works by repeatedly dividing the search interval in half and checking whether the square of the middle value is less than, equal to, or greater than x. This reduces the number of checks dramatically compared to the brute-force approach.

Solution Approach

We use a binary search approach to efficiently find the integer square root:

1. Initialize pointers: Set left to 0 and right to x. These pointers represent the current search range.
2. Iterate with binary search: While left is less than or equal to right:
   • Compute mid as the average of left and right.
   • Calculate mid * mid and compare it to x:
   • If mid * mid is equal to x, mid is the answer.
   • If mid * mid is less than x, move left up to mid + 1 (look for a larger square root).
   • If mid * mid is greater than x, move right down to mid - 1 (look for a smaller square root).
3. Return the result: When the loop ends, right will be at the largest integer whose square is less than or equal to x. Return right.

This method avoids overflow by using integer division and prevents unnecessary calculations.

Example Walkthrough

Let's walk through an example with x = 8:

1. Initialize left = 0, right = 8.
2. First iteration:
   • mid = (0 + 8) // 2 = 4
   • 4 * 4 = 16 > 8, so set right = 3
3. Second iteration:
   • mid = (0 + 3) // 2 = 1
   • 1 * 1 = 1 < 8, so set left = 2
4. Third iteration:
   • mid = (2 + 3) // 2 = 2
   • 2 * 2 = 4 < 8, so set left = 3
5. Fourth iteration:
   • mid = (3 + 3) // 2 = 3
   • 3 * 3 = 9 > 8, so set right = 2
6. Now left > right (3 > 2), so we exit and return right = 2.

This matches the expected answer, since the integer square root of 8 is 2.

Time and Space Complexity

• Brute-force: O(√x) time, O(1) space. This is because we would check every integer up to √x.
• Binary search: O(log x) time, O(1) space. Each step cuts the search range in half, leading to a logarithmic number of steps.

The binary search method is much more efficient, especially for large values of x.

Summary

The Sqrt(x) problem is a classic example of using binary search to optimize a search for a value within a monotonic function. By leveraging the properties of square roots and binary search, we can efficiently find the integer square root in logarithmic time without using built-in functions. This approach is elegant, avoids overflow, and is much faster than brute-force for large inputs.

Code Implementation

class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x
        left, right = 1, x // 2
        while left <= right:
            mid = (left + right) // 2
            if mid * mid == x:
                return mid
            elif mid * mid < x:
                left = mid + 1
            else:
                right = mid - 1
        return right
      

class Solution {
public:
    int mySqrt(int x) {
        if (x < 2) return x;
        int left = 1, right = x / 2, ans = 0;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if ((long long)mid * mid == x) {
                return mid;
            } else if ((long long)mid * mid < x) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return right;
    }
};
      

class Solution {
    public int mySqrt(int x) {
        if (x < 2) return x;
        int left = 1, right = x / 2;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if ((long)mid * mid == x) {
                return mid;
            } else if ((long)mid * mid < x) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return right;
    }
}
      

var mySqrt = function(x) {
    if (x < 2) return x;
    let left = 1, right = Math.floor(x / 2);
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (mid * mid === x) {
            return mid;
        } else if (mid * mid < x) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return right;
};