Skip to main content

69. Sqrt(x)

easyAsked at Goldman Sachs

Compute the integer part of sqrt(x) without using a built-in sqrt function. Goldman Sachs uses this to test whether you can implement binary search on the answer space — the fundamental quant interview skill.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Goldman Sachs loops.

  • Glassdoor (2026-Q1)— Goldman Sachs Strats and Engineering reports list Sqrt(x) as a 'binary search on the answer space' question.
  • LeetCode Discuss (2025-10)— Sqrt(x) sits in the top-20 of LeetCode's Goldman Sachs company tag.

Problem

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.

Constraints

  • 0 <= x <= 2^31 - 1

Examples

Example 1

Input
x = 4
Output
2

Example 2

Input
x = 8
Output
2

Explanation: sqrt(8) is 2.82..., rounded down is 2.

Approaches

1. Linear scan

Try k = 0, 1, 2, ... until k*k > x; return k-1.

Time
O(sqrt(x))
Space
O(1)
function mySqrtLinear(x) {
  let k = 0;
  while ((k + 1) * (k + 1) <= x) k++;
  return k;
}

Tradeoff: Correct but O(sqrt(x)) — at x = 2^31 - 1 it does ~46000 iterations, which times out on Goldman's HackerRank timer. Mention briefly then move to binary search.

2. Binary search on the answer (optimal)

The answer is in [0, x]. Binary-search for the largest k such that k*k <= x.

Time
O(log x)
Space
O(1)
function mySqrt(x) {
  if (x < 2) return x;
  let lo = 1, hi = Math.floor(x / 2);
  while (lo <= hi) {
    const mid = Math.floor(lo + (hi - lo) / 2);
    const sq = mid * mid;
    if (sq === x) return mid;
    if (sq < x) lo = mid + 1;
    else hi = mid - 1;
  }
  return hi;
}

Tradeoff: O(log x) — about 31 iterations at INT_MAX. The 'return hi' at the end is the part Goldman wants to see — after the loop, hi is the floor of the true square root.

3. Newton's method

Iterate x_{n+1} = (x_n + x / x_n) / 2 until convergence.

Time
O(log x)
Space
O(1)
function mySqrtNewton(x) {
  if (x < 2) return x;
  let r = x;
  while (r * r > x) {
    r = Math.floor((r + Math.floor(x / r)) / 2);
  }
  return r;
}

Tradeoff: Converges quadratically — fewer iterations than binary search in practice. Mention as a bonus to show numerical-analysis chops; binary search is what most Goldman interviewers expect.

Goldman Sachs-specific tips

Goldman Sachs uses Sqrt(x) specifically to test 'binary search on the answer space' as a concept. The pivot from 'I need sqrt' to 'I'll binary-search for the largest k with k*k <= x' is the moment that earns the credit. The lo + (hi - lo) / 2 instead of (lo + hi) / 2 detail is the small thing Goldman looks for — overflow safety in 32-bit languages.

Common mistakes

  • Overflow on mid*mid for large x — in JS this is fine due to 64-bit floats, but Goldman's Java/C++ rounds will require BigInteger or the (long) cast.
  • Returning lo instead of hi after the loop — at exit, hi < lo and hi is the floor of sqrt.
  • Forgetting the x < 2 short-circuit, which infinite-loops on x = 0 if lo and hi start at 1 and 0.

Follow-up questions

An interviewer at Goldman Sachs may pivot to one of these next:

  • Compute sqrt(x) to k decimal places. (Continue binary search past the integer boundary on a scaled value.)
  • Compute cube root of x. (Same template — binary search the answer.)
  • Newton-Raphson convergence rate vs binary search — when is Newton better?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why does Goldman ban Math.sqrt or pow?

Because the question is about your ability to do binary search on the answer space — not your knowledge of the standard library. The 'no exponent function' rule is in the problem statement specifically to force this.

Why mid * mid <= x and not (mid + 1) * (mid + 1) <= x?

Both work; they're different invariants. The version above keeps the invariant 'lo is a candidate answer that might be too small, hi is a candidate that might be too large' and reads cleanly. Either is correct.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Sqrt(x) and other Goldman Sachs interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →