Skip to main content

69. Sqrt(x)

easy

Compute floor(sqrt(x)) using only integer arithmetic. The classic binary-search-on-answer problem — and a popular Newton's-method demo.

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) 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.

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

Binary search the largest integer mid in [0, x] such that mid * mid <= x.

Hint 2

Watch overflow: mid * mid can exceed 2^31 - 1 when x is near the upper bound. Use 64-bit math or compare mid against x / mid.

Hint 3

Standard template: lo = 0, hi = x. While lo <= hi: mid = (lo + hi) / 2; if mid <= x / mid then ans = mid, lo = mid + 1; else hi = mid - 1.

Hint 4

Newton's method: x_{k+1} = (x_k + x / x_k) / 2. Stop when the sequence stops decreasing. Converges in a handful of iterations.

Solution approach

Reveal approach

Binary search. lo = 0, hi = x (or 46341 for x up to 2^31 - 1 if you want a tighter bound). Maintain answer = 0. While lo <= hi: mid = lo + (hi - lo) / 2. Compare mid <= x / mid (overflow-safe alternative to mid * mid <= x). If yes, record answer = mid and lo = mid + 1; else hi = mid - 1. Return answer. O(log x) time, O(1) space. Newton's method variant: start guess = x; while guess > x / guess set guess = (guess + x / guess) / 2; return guess. Converges quadratically and is the standard textbook fast version.

Complexity

Time
O(log n)
Space
O(1)

Related patterns

  • binary-search
  • math

Related problems

Asked at

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

  • Amazon
  • Microsoft
  • Apple
  • Bloomberg

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →