Why it works
- 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.
- 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.
- 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 ↗