Sqrt(x)
Problem Statement
You are given a non-negative integer x. Return its square root rounded down to a whole number.
In other words, return the biggest integer r such that r · r ≤ x.
You may not use any built-in power or square-root function, such as pow(x, 0.5) or sqrt(x).
A single integer x.
The largest integer r with r · r ≤ x.
2 · 2 = 4, and 3 · 3 = 9 is too big.
The real square root is 2.828…, which rounds down to 2. Check: 2 · 2 = 4 ≤ 8, but 3 · 3 = 9 > 8.
- • 0 ≤ x ≤ 2^31 − 1
Pattern Recognition Clues
Recognising these key signals in the problem description immediately identifies the pattern:
Approach Complexity Ladder
Try r = 0, 1, 2, … until (r + 1)² is bigger than x
Binary search r in [0, x] for the last r with r·r ≤ x
Start with r = 0. While the next number r + 1 still has a square ≤ x, step up. When (r + 1)² is too big, r is the answer.
Recognition rule for this sub-pattern:
Unlock Complete Visual Walkthrough & Optimal C++
The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.
First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.
How this concept connects to System Design & C++ Systems
Top engineering interviews test whether you understand how algorithms like Binary Search translate into production architectures and low-level memory mechanics.