The challenge
Return floor(√x), the largest nonnegative integer whose square is at most x.
0 ≤ x ≤ 10⁹. This is an integer search with no floating-point approximation.
Example
x = 26 → 5, because 5² ≤ 26 < 6².
Use the walkthrough below to inspect the input and each state change.
See Floor square root, step by step
Inspect the comparison, the invariant, and the next boundary.
Answer-space searchx = 26
Tested candidate / qualifying inputResolved positionParameters shown above
- Left
- 1
- Middle
- —
- Right
- 26
Step 01 / 7
Search the answer range
The candidate is a number, rather than an input index. Keep the largest feasible value.
left = 1; right = 26Recorded result so far
Not resolved
View exact input
Input: [] · x = 26
Put it into code
Search the last true value of mid² ≤ x. Compare mid ≤ x / mid using integer division to avoid overflowing a product.
Indices are zero-based. C++ uses C++17 or later.
def integer_sqrt(x):
# 0 <= x <= 10**9
if x == 0:
return 0
left, right, answer = 1, x, 0
while left <= right:
mid = left + (right - left) // 2
if mid <= x // mid:
answer = mid
left = mid + 1
else:
right = mid - 1
return answerlong long integer_sqrt(long long x) {
if (x == 0) return 0;
long long left = 1, right = x, answer = 0;
while (left <= right) {
long long mid = left + (right - left) / 2;
if (mid <= x / mid) {
answer = mid;
left = mid + 1;
} else right = mid - 1;
}
return answer;
}