Sqrt(x)

The problem. Given a non-negative integer x, return the square root of x rounded down to the nearest integer. You may not use any built-in exponent function or operator such as Math.sqrt or x ** 0.5.

Example

x = 4  ->  2
x = 8  ->  2   (the real root is 2.828...)
x = 0  ->  0
x = 2147483647  ->  46340

The idea: search the numbers, not an array

The answer is a whole number between 0 and x, and the question "is m * m <= x?" is yes for small m and no once m passes the root — it flips once. So binary search the candidates 0..x for the last yes. Each step halves the range, so even x = 2³¹ − 1 takes only about 31 steps. This is binary search on the answer in its simplest form.

1. Count up

1function mySqrt(x) {2  let k = 0;3  while ((k + 1) * (k + 1) <= x) k++;   // grow k while the next square still fits4  return k;5}

Time O(√x), space O(1). About 46,000 steps for the largest input — fast enough here, but it doesn't scale.

2. Binary search for the last m with m² <= x

1function mySqrt(x) {2  let low = 0;3  let high = x;4  let answer = 0;5  while (low <= high) {6    const mid = low + Math.floor((high - low) / 2);7    if (mid * mid <= x) {8      answer = mid;                          // mid fits: remember it, then look for a bigger one9      low = mid + 1;10    } else {11      high = mid - 1;                        // mid is too big12    }13  }14  return answer;15}

Time O(log x), space O(1). Keeping a separate answer is a handy way to find a last yes with the classic loop: every yes is a candidate, and the loop keeps looking right for a better one.

3. Newton's method

A different idea from numerical analysis: start with a guess r and replace it with the average of r and x / r. If r is too big, x / r is too small, and their average is much closer. In integers, repeat while r * r > x. It converges very fast — each step roughly doubles the number of correct digits.

1function mySqrt(x) {2  let r = x;3  while (r * r > x) r = Math.floor((r + Math.floor(x / r)) / 2);   // average r and x / r4  return r;5}

Time O(log x), space O(1) — and in practice fewer steps than binary search. Binary search is the expected interview answer; Newton's method is a great follow-up.

Comparing the approaches

Edge cases to test

Variations