Sqrt(x)

Loading...LeetCode

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.

You must not use any built-in exponent function or operator.

• For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.

Example 1:

Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.

Example 2:

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned.

Constraints:

• 0 <= x <= 231 - 1

You can solve this problem using a binary search approach to find the square root of the given non-negative integer. Here's a JavaScript implementation:

function mySqrt(x) {
    if (x === 0) return 0;
    
    let left = 1;
    let right = Math.floor(x / 2) + 1;

    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        const square = mid * mid;

        if (square === x) {
            return mid;
        } else if (square < x) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    return left - 1;
}

// Test cases
console.log(mySqrt(4)); // Output: 2
console.log(mySqrt(8)); // Output: 2

This implementation performs a binary search within the range [1, x / 2] to find the square root. At each step, it calculates the square of the middle element and compares it with the given number. If the square is equal to the given number, it returns the middle element. If the square is less than the given number, it updates the left boundary to be the middle element plus one. If the square is greater than the given number, it updates the right boundary to be the middle element. Finally, it returns the left boundary minus one, which represents the square root rounded down to the nearest integer.