Skip to main content

69. Sqrt(x)

easyAsked at Intel

Compute the integer square root of x without using built-in sqrt. Intel asks this because the two optimal approaches — binary search and Newton's method — both show up in fixed-point math libraries Intel ships, and the candidate who can articulate the convergence rate of Newton's method (quadratic) is the senior numerical-software signal.

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

Source citations

Public interview reports confirming this problem appears in Intel loops.

  • Glassdoor (2026-Q1)— Intel SWE-II onsite reports cite sqrt(x) as a 25-minute math/binary-search hybrid round.
  • GeeksforGeeks (2025-08)— Intel Interview Experience archives list sqrt(x) under 'math + binary search' standard asks.
  • Reddit r/cscareerquestions (2025-10)— Intel hardware-engineering thread describes this with the Newton's-method follow-up.

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

Explanation: The square root of 4 is 2, so we return 2.

Example 2

Input
x = 8
Output
2

Explanation: The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned.

Approaches

1. Linear search (brute)

Iterate i from 0 upward; stop when (i+1)*(i+1) > x.

Time
O(sqrt(x))
Space
O(1)
function mySqrtBrute(x) {
  if (x < 2) return x;
  let i = 1;
  while ((i + 1) * (i + 1) <= x) i++;
  return i;
}

Tradeoff: Always works but slow: at x = 2^31, this is ~46,000 iterations. Acceptable on this constraint but never the answer Intel wants.

2. Binary search (optimal — search-based)

Search for the largest mid such that mid*mid <= x in [0, x].

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

Tradeoff: Logarithmic, predictable, no floating point. The 'safe' answer that always lands. Beware mid*mid overflow in C/C++ for large x — use long, or `mid > x / mid` as the comparison.

3. Newton's method (optimal — numerical)

Iterate r = (r + x/r) / 2 until convergence. Each step roughly doubles the number of correct digits (quadratic convergence).

Time
O(log x) iterations, each O(1)
Space
O(1)
function mySqrt(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: Fewer iterations than binary search in practice (~5 to converge from x for 32-bit inputs). The reciprocal-and-average shape is the same iteration the hardware FSQRT instruction approximates internally.

Intel-specific tips

Intel interviewers want you to discuss BOTH approaches. State 'binary search gives log x with no floating point, Newton's method gives the same Big-O with a smaller constant because it converges quadratically'. If they push further, mention that the x86 FSQRT instruction uses a hardware-tuned variant of Newton's method internally — the same iteration as the software version, just in fewer cycles.

Common mistakes

  • Using `mid * mid <= x` in C/C++ for x near INT_MAX — mid*mid overflows. Fix: cast mid to long or use `mid <= x / mid` (with mid != 0 guard).
  • Newton's method without an integer guard — pure float Newton might oscillate around the integer answer; the `Math.floor` keeps it monotone and terminating.
  • Returning floor incorrectly when x = 1 — make sure your base case handles x < 2 cleanly.

Follow-up questions

An interviewer at Intel may pivot to one of these next:

  • Valid Perfect Square (LC 367) — same idea, return bool instead of floor.
  • Compute sqrt to k decimal places. (Newton's method natively — just don't floor; iterate while delta > 10^-k.)
  • How does the hardware FSQRT instruction work? (Iterative Newton refinement on a seed produced by a small lookup table.)

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 is Newton's method 'quadratically convergent' and what does that mean here?

Each iteration roughly doubles the number of correct digits. So if you start with 1-digit accuracy and want 10 digits, that's ~4 iterations (1 → 2 → 4 → 8 → 16+). For 32-bit ints, ~5 iterations suffice from any reasonable starting point.

Should I use binary search or Newton's in an interview?

Binary search if you only have one shot — it's simpler, no oscillation risks, no overflow if you compare via division. Newton's if the interviewer asks 'can you do better than log2(x) iterations?' — Newton's gives ~log2(log2(x)) for the same precision.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →