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 Sam K., 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

More Binary Search practice problems

See all Binary Search problems →