Solving Leetcode 69: Sqrt(x) (JavaScript)

Today, I’m working on learning about how to solve Leetcode 69: Sqrt(x)

The Problem:

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.
Note: You are not allowed to use any built-in exponent function or operator, such as pow(x, 0.5) or x ** 0.5.
Example 1:
Input: x = 4
Output: 2
Example 2:
Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.

The problem asks us to find the square root of x while removing any decimals. We should only be returning the whole number.

The first thing we’re going to do is declare a left and right variable.

We will have the left = 0, and the right = x.

function mySqrt(x) {
  let left = 0;
  let right = x;
}

From the problem statement, we know that x cannot be a negative number. We also know that the square root of 0 and 1 are 0 and 1.

So we can use an if statement to take care of these cases.

If the number is less than or equal to 1, we will return that number.

function mySqrt(x) {
  let left = 0;
  let right = x;
  if (x <= 1){
    return x;
  }

}

Photo by JESHOOTS.COM on Unsplash

Let’s get to the meat of the problem.

We want to find the square root of x.

We’ll use binary search to divide the number into two halves and compare it to the middle.

While the left side is less than the right side, we will let the middle be the mid-point between them and round using Math.floor( ).

I will also declare square, which is middle * middle.

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

   }
}

If square is equal to the number we’re looking for, we return the middle number.

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

If square is less than the number we’re looking for, then the answer we’re looking for has to be on the right side of the middle. Therefore, we change the value of left to middle + 1.

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

Else, the number must be on the left and we return left -1.

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

✨✨✨And that’s it!

Tish⚡️🎧🌙