DEV Community

codingpineapple
codingpineapple

Posted on

LeetCode 69. Sqrt(x) (javascript solution)

Description:

Given a non-negative integer x, compute and return the square root of x.

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

Solution:

Time Complexity : O(log(n))
Space Complexity: O(1)

// Binary search approach
var mySqrt = function(x) {
    let left = 1;
    let right = x;
    // The square root of 0 or 1 is itself
    if(x < 2) return x;

    // Use binary search to find the square root or the whole number closest to the square root
    while(left < right) {
        // Find the mid point between left and right
        const mid = Math.floor((left + right) / 2)
        // Return the mid point if this is the square root
        if(mid*mid === x) return mid
        // If mid squared is greater than x then the answer must be on the left half of mid
        else if(mid*mid >x) right = mid
        // If mid squred is less than x then the answer must be on the right half of mid
        else left = mid+1
    }
    return left - 1
};
Enter fullscreen mode Exit fullscreen mode

Discussion (3)

Collapse
vishal590 profile image
vishal

Can anyone explain this code. I know binary search but didn't get this point -

if(mid*mid === x) return mid
// If mid squared is greater than x then the answer must be on the left half of mid
else if(mid*mid >x) right = mid
// If mid squred is less than x then the answer must be on the right half of mid
else left = mid+1
}
return left - 1

Collapse
maparr profile image
Maksym Parfenov
if(mid*mid === x) return mid
Enter fullscreen mode Exit fullscreen mode

the task says, we need
Input: x = 4 // input
Output: 2 // we have to return

else if(mid*mid >x) right = mid
Enter fullscreen mode Exit fullscreen mode

if the mid * mid ( target ) is bigger we're going left side of the binary search ( in the case with numbers, not arrays, we're doing like this, if mid before was 4 , it is our input in first iteration, new value will be 2;

else left = mid+1
Enter fullscreen mode Exit fullscreen mode

says, we going to the right side of the binary search, and 2 + 1 = 3 and we are going to search again through while

Collapse
vishal590 profile image
vishal

thanks for reply