#69 Sqrt(x)
frequently reported atByteDance / TikTokBloombergAmazonGoogleAppleMeta
the problem
In plain words
Return ⌊√x⌋ for a non-negative int x without using built-in power or sqrt functions.
in x = 4
out 2
in x = 8
out 2
√8 ≈ 2.83, rounded down.
- 0 ≤ x ≤ 2³¹ − 1
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternBinary search on the answer
"Does r·r ≤ x?" is true for small r and false for large r — a sorted yes/no answer space. Binary search it: O(log x) instead of O(√x).
solutions
From brute force to optimal
Increase r while (r + 1)² ≤ x.
- r = 0.
- While (r+1)·(r+1) ≤ x (in long): r++.
r climbs to ⌊√x⌋ = 46,340 for the largest int.
One counter.
class Solution { public int mySqrt(int x) { long r = 0; while ((r + 1) * (r + 1) <= x) r++; // long: (r+1)^2 overflows int near 46341 return (int) r; }}Search the largest r in [0, x] with r·r ≤ x.
- lo = 0, hi = x.
- mid fits → remember it, go right; too big → go left.
- Return the last mid that fit.
The range halves each step: ≤ 32 steps for any int.
A few longs.
class Solution { public int mySqrt(int x) { long lo = 0, hi = x, ans = 0; while (lo <= hi) { long mid = lo + (hi - lo) / 2; if (mid * mid <= x) { ans = mid; lo = mid + 1; } // mid fits: try bigger else hi = mid - 1; // mid too big: go smaller } return (int) ans; }}r ← (r + x/r) / 2 converges to √x very quickly.
- r = x.
- While r·r > x: r = (r + x / r) / 2.
- Return r.
From r = x it roughly halves until close to √x, then converges quadratically.
One long.
class Solution { public int mySqrt(int x) { if (x < 2) return x; long r = x; while (r * r > x) r = (r + x / r) / 2; // integer Newton step, decreases until r*r <= x return (int) r; }}in the room
How to say it in the interview
talk track
- Point out the overflow trap first: mid·mid overflows int for mid > 46,340 — use long.
- Explain why binary search applies: the predicate r·r ≤ x is monotonic.
traps
- Computing mid * mid in int.
- Returning lo instead of the last mid that fit (off-by-one).
what they ask next
Follow-ups
Valid Perfect Square (LC 367)?
Same binary search; return true if some mid has mid·mid == x exactly.
before you submit
Edge cases to test
- x = 0 and x = 1: the answer is x itself.
- x = 2,147,483,647: mid·mid overflows an int once mid > 46,340 — use long.
- A perfect square (16 → 4) next to one less (15 → 3): check the rounding down.
practise next
Similar problems
- #875Koko Eating BananasMediumin Binary Search
- #1011Capacity To Ship Packages Within D DaysMediumin Binary Search