easy

Sqrt(x)

Compute the integer square root of a number without using built-in power functions.

1. Define the problem

Sqrt(x)

Given a whole number x that is zero or larger, return the square root of x, rounded down to a whole number. You are not allowed to use a built-in power or square-root function. Rounded down means you drop anything after the decimal point: the square root of 8 is about 2.83, so the answer is 2. Instead of trying every number from 1 upwards, guess a number, square it, and throw away half the remaining guesses each time based on whether the square was too small or too big.

Constraints

  • 0 ≤ x ≤ 231 - 1
  • x is a whole number
  • The answer is rounded down

Example

Inputx = 8
Output2

Explanation The exact square root of 8 is about 2.828. Rounded down to a whole number that is 2.

2. Know the words first

In plain terms

Square root
The number that, multiplied by itself, gives you the original number. 5 times 5 is 25, so the square root of 25 is 5.
Binary search
A way of finding an answer inside a sorted range of possibilities by checking the middle one and discarding the half that cannot contain the answer.
Search range
The set of guesses still worth checking, tracked with two numbers: low (the smallest guess left) and high (the largest guess left).
3. Visualize the solution

Guess a square root, then halve the remaining guesses

Guess a square root, then halve the remaining guesses
Statusinit

Looking for the square root of 8, so guesses 1 to 4 are in play.

What happens in this step

x = 8
low = 1, high = floor(8 / 2) = 4

No whole number above half of x can be its square root, so guesses 5 to 8 are ruled out before we start. The box covers guesses 1 to 4.
Step 1 of 4

Steps to visualize

  1. The row is the list of possible answers 1 to 8; each cell shows that guess multiplied by itself.
  2. The box marks the guesses still in play, from low to high.
  3. Take the middle guess and square it.
  4. If the square equals x, that guess is the answer.
  5. If the square is smaller than x, remember the guess and move low above the middle.
  6. If the square is bigger than x, move high below the middle.
  7. When the range runs out, the last guess that was too small is the rounded-down answer.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Guess a square root, then halve the remaining guesses
Statusinit

Looking for the square root of 8, so guesses 1 to 4 are in play.

What happens in this step

x = 8
low = 1, high = floor(8 / 2) = 4

No whole number above half of x can be its square root, so guesses 5 to 8 are ruled out before we start. The box covers guesses 1 to 4.
Step 1 of 4
5. Solution

Solution

solution.tsTypeScript
function mySqrt(x) {
  if (x < 2) {
    return x;
  }

  let low = 1;
  let high = Math.floor(x / 2);
  let answer = 1;

  while (low <= high) {
    const mid = low + Math.floor((high - low) / 2);
    const square = mid * mid;

    if (square === x) {
      return mid;
    }
    if (square < x) {
      answer = mid;
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return answer;
}
Time
O(log x)
Space
O(1)
6. Test cases

Test cases

InputExpectedCovers
x = 82example from the description, answer rounded down
x = 42x is an exact square
x = 00smallest possible input
x = 11x below 2, handled before the search starts
x = 153answer sits between two whole squares
x = 214739560046340very large input where scanning one by one would be far too slow

Keep reading