Square Root

Given a non-negative integer n, return the integer square root — the largest integer r with r*r <= n — without using any floating-point sqrt function.

squareRoot(n)

Examples

squareRoot(16)  // → 4
squareRoot(8)   // → 2   (2*2=4 <= 8 < 9 = 3*3)
squareRoot(0)   // → 0

Walkthrough

Thinking it through

There's no built-in square root here, so turn the problem into something binary search can attack: instead of computing the answer directly, test a candidate answer — given a guess r, can you cheaply check if it's valid, and which way to adjust?

Reframing as a monotonic condition

Define "is r * r <= n?" for candidate r. As r increases from 0 to n, this starts true and, once r's square exceeds n, becomes false and stays false. True for a prefix of [0, n], false for the rest — flipping exactly once. That's the monotonic structure binary search needs, except you're searching over possible answers, not stored array values.

Why checking every candidate one at a time is wasteful

You could increment r from 0 until its square exceeds n, then back off. That works, but takes as many steps as the answer itself — wasteful for large n when the monotonic structure lets you rule out huge swaths with one comparison.

The binary search approach

Maintain [lo, hi] starting at [0, n]. Test the middle: if its square doesn't exceed n, it's valid — record it as best-so-far, and search higher (lo = mid + 1) to see if you can do better. If its square exceeds n, it and everything larger is disqualified — search lower (hi = mid - 1).

Each comparison rules out roughly half the remaining range, just like array binary search — except the "array" is the implicit range of integers, computed on the fly.

Why this is efficient

Since the candidate range starts at size roughly n and halves each comparison, the number of comparisons is proportional to log(n), not n — a big improvement over incrementing one candidate at a time.

main.py

Auto-saved

Console

Press Run to execute your code, or Submit to test and complete this problem.