Skip to main content

69. Sqrt(x)

easy

Compute the integer square root of x without using a built-in sqrt function. The first taste of 'binary-search on the answer' that everyone should solve before tackling harder variants.

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

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) or x ** 0.5 in code.

Constraints

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

Examples

Example 1

Input
x = 4
Output
2

Example 2

Input
x = 8
Output
2

Explanation: The square root of 8 is 2.828..., truncated to 2.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

The answer lies in [0, x]. For x >= 2, a tighter upper bound is x / 2.

Hint 2

Search for the largest integer k such that k * k <= x. That's an upper-bound binary search.

Hint 3

Beware of integer overflow when computing mid * mid for x near 2^31. Use long/64-bit arithmetic or compare mid against x / mid instead.

Solution approach

Reveal approach

Binary search for the largest k where k * k <= x. Initialize lo = 0 and hi = x (or x / 2 for x >= 2). While lo <= hi, compute mid = lo + (hi - lo) / 2. To avoid overflow, compare mid against x / mid instead of computing mid * mid in 32-bit. If mid <= x / mid, mid is a feasible answer; record it and try larger (lo = mid + 1). Otherwise hi = mid - 1. Return the last recorded feasible mid. The predicate (k*k <= x) is monotonic in k, which is the universal precondition for binary-search-on-answer. O(log x) iterations, O(1) space. Newton's method is asymptotically faster but binary search is the interview-standard answer because it transfers to dozens of other problems.

Complexity

Time
O(log x)
Space
O(1)

Related patterns

  • binary-search
  • binary-search-on-answer

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Apple
  • Bloomberg
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Sqrt(x) and Binary Search problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →