Sqrt(x)

Easy#69search the answer

You get a non-negative integer x. Return its square root rounded down, without a built-in power or root function. Our example: x = 20 — the answer is 4: 4 · 4 = 16 fits under 20, 5 · 5 = 25 does not.

69 Sqrt(x)Walkthrough · 1×

Example: x = 20. The cells are the candidate roots 1..10; we look for the largest k with k · k <= 20.

candidate roots k12345678910mid · mid—
root still possiblemiddle, checked nowruled outthe root

20 is not below 2: search

01/21
restart · back · play · step
Speed
1function mySqrt(x):
2 if x < 2:
3 return x
4 lo = 1
5 hi = floor(x / 2) // the root is at most x / 2
6 while lo < hi:
7 mid = ceil((lo + hi) / 2) // round up
8 if mid * mid <= x:
9 lo = mid // mid fits: keep it
10 else:
11 hi = mid - 1
12 return lo
state
x
20
lo
–
hi
–
mid
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Squares grow: 1, 4, 9, 16, 25, … So the checks "k · k <= x" go yes, yes, …, no, no, and the answer is the last yes. Binary search finds that border.
  2. If mid fits, it may be the answer, so lo = mid keeps it. If it does not, nothing above it fits either: hi = mid − 1.
  3. Since lo = mid can leave lo where it was, mid is rounded up: with two candidates left it lands on the upper one, and the range always shrinks.

Complexity

Time O(log x): the range 1..x / 2 halves on every step. Memory O(1). For a large x, mid · mid overflows a 32-bit integer: compare mid with x / mid instead, or count in 64 bits.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.