We use analytics and advertising cookies to understand how the site is used and whether our ads on Facebook and Instagram work. They are set only if you accept. See our Privacy Policy for details.
Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.
You must not use any built-in exponent function or operator (such as Math.sqrt or ** or x ** 0.5).
An easy binary search problem, graded against 8 test cases (5 of them hidden).
Halving a search space each step - on sorted arrays, and on answers themselves.
Reach for it when you see: A sorted input, or a monotonic "is this value feasible?" predicate you can binary search over.
More Binary Search problems →Use binary search in the range [0, x]. For each midpoint, check if mid * mid <= x. Track the largest valid mid as the answer.
If mid * mid equals x, return mid. If mid * mid < x, search the right half. If mid * mid > x, search the left half.
The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.
Read off this problem's own test suite, so these are the cases a submission actually has to survive.
These apply to the pattern as a whole, not just this problem.