Sqrt(x) Explained

Problem Statement

Given a non-negative integer x, compute and return the integer square root of x, i.e., the largest integer y such that y * y <= x. This problem tests your ability to implement efficient algorithms like binary search to avoid using built-in math functions.

Example

Input: x = 8

Output: 2

Explanation: The square root of 8 is approximately 2.828, so the integer part is 2.

Code

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

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.mySqrt(8)); // 2
    }
}
            

def my_sqrt(x):
    if x == 0:
        return 0
    left, right = 1, x
    while left <= right:
        mid = (left + right) // 2
        square = mid * mid
        if square == x:
            return mid
        if square < x:
            left = mid + 1
        else:
            right = mid - 1
    return right

# Example usage
print(my_sqrt(8))  # 2
            

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

// Example usage
console.log(mySqrt(8)); // 2
            

Explanation

• Handle the base case: if x is 0, return 0.
• Use binary search to find the largest integer mid where mid * mid <= x.
• Adjust the search range based on whether mid * mid is less than or greater than x.
• Return the right pointer, which is the floor of the square root.

Note