69. Sqrt(x)

Description

The task is to find the integer square root of a non-negative integer x. The integer square root of x is the largest integer r such that r^2 is less than or equal to x.

Intuition

The problem can be solved efficiently using binary search. Since the square root function is monotonically increasing, we can use binary search to find the integer part of the square root.

Approach

1. Initialization: - Handle the special case where x is 0 by returning 0 immediately. - Initialize left to 1 and right to x. These represent the search range for the integer square root.
2. Binary Search: - Perform binary search while left is less than or equal to right. - Calculate mid as the average of left and right. - Compute mid_squared as mid * mid. - Compare mid_squared with x: - If mid_squared is equal to x, mid is the exact integer square root, so return mid. - If mid_squared is less than x, update result to mid (since mid is a candidate for the integer square root) and search the right half by setting left to mid + 1. - If mid_squared is greater than x, search the left half by setting right to mid - 1.
3. Return the Result: - After the loop, result contains the integer part of the square root.

Complexity

Time Complexity:

O(log x), where x is the input number. The binary search algorithm halves the search space in each iteration, leading to a logarithmic time complexity.

Space Complexity:

O(1). The algorithm uses a constant amount of extra space beyond the input size.

Code

C++

class Solution {
public:
    int mySqrt(int x) {
        if (x == 0) return 0;  // Edge case for zero
        int beg = 1, end = x, ans = 0;  // Start with 1 because sqrt(0) is 0
        while (beg <= end) {
            int mid = beg + (end - beg) / 2;
            long long midSquared = static_cast(mid) * mid;  // Avoid overflow
            
            if (midSquared == x) {
                return mid;
            } else if (midSquared < x) {
                ans = mid;  // Record the last valid mid
                beg = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return ans;  // Return the integer part of sqrt(x)
    }
};

Python

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

Java

class Solution {
    public int mySqrt(int x) {
        if (x == 0) return 0; // Edge case for zero
        
        long left = 1, right = x, result = 0; // Use long to prevent overflow
        
        while (left <= right) {
            long mid = left + (right - left) / 2;
            long midSquared = mid * mid;
            
            if (midSquared == x) {
                return (int) mid;
            } else if (midSquared < x) {
                result = mid; // Record the last valid mid
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return (int) result; // Return the integer part of sqrt(x)
    }
}

JavaScript

var mySqrt = function(x) {
    var beg = 0, end = x, ans = 0;
    while(beg <= end) {
        var mid = Math.floor((beg + end)/2);
        if(mid*mid > x) {
            end = mid - 1;
        }
        else { // mid*mid <= x
            ans = mid;
            beg = mid + 1;
        }
    }
    return ans;
};