Integer square root with no built-ins: binary search the answer, square the middle, and keep the largest value whose square still fits.
▼The problem
LeetCode 69 (Easy). Given a non-negative integer x (0 ≤ x ≤ 2³¹ − 1), return the square root of x rounded down to the nearest integer, without any built-in exponent function or operator (no pow(x, 0.5), no x ** 0.5, no sqrt).
Examples (LeetCode's): x = 4 → 2; x = 8 → 2 (the root is 2.828…, rounded down).
The solution
def mySqrt(x):
lo, hi = 0, x
ans = 0
while lo <= hi:
mid = (lo + hi) // 2
if mid * mid <= x:
ans = mid # fits: record it
lo = mid + 1 # search higher
else:
hi = mid - 1 # search lower
return ansTranscript
Square Root of x. Given a non-negative whole number x, return its square root, rounded down, without a built-in power or square root. With x saplings, how wide is the biggest square orchard you can plant?
With four saplings, a two by two square uses them all: two. With eight, three by three would need nine. The true root is two point eight two eight, rounded down to two.
The slow way tries every width: zero, one, two, until the next square needs more than x. For the largest input, over two billion, that's forty-six thousand three hundred forty-one checks.
Better: the answer lies between zero and x, and the test flips only once. Small squares fit; once one is too big, every bigger one is too. So binary search the answer. Try the middle width. If mid times mid fits, the answer is at least mid: record it and search higher. If not, search lower.
In code, low and high close in until they cross. With fixed-size integers, compare mid with x divided by mid to avoid overflow. Newton's method, which refines a guess, works too.
Let's try ninety-nine. Forty-nine needs over two thousand. Twenty-four, then eleven: still too big. Five fits: record it. Eight fits, then nine: eighty-one. Ten needs a hundred: too big. Low passes high, so the answer is nine.
Each check halves the range: order log x time, at most thirty-one checks, not forty-six thousand. A few variables: constant space.
Search the answer, test the square, keep the last fit. That's Square Root of x.