Sqrt(x) - Problem
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.
Important: You must not use any built-in exponent function or operator. For example, do not use pow(x, 0.5) in C++ or x ** 0.5 in Python.
Input & Output
Example 1 — Perfect Square
$
Input:
x = 4
›
Output:
2
💡 Note:
The square root of 4 is exactly 2, so we return 2
Example 2 — Non-Perfect Square
$
Input:
x = 8
›
Output:
2
💡 Note:
√8 = 2.828..., rounded down to nearest integer is 2
Example 3 — Edge Case Zero
$
Input:
x = 0
›
Output:
0
💡 Note:
The square root of 0 is 0
Constraints
- 0 ≤ x ≤ 231 - 1
- Must not use built-in exponent functions
Visualization
Tap to expand
Understanding the Visualization
1
Input
Given non-negative integer x=8
2
Process
Find largest integer whose square ≤ x
3
Output
Return 2 (since 2²=4≤8 but 3²=9>8)
Key Takeaway
🎯 Key Insight: Use binary search to efficiently find the largest integer whose square doesn't exceed the input
💡
Explanation
AI Ready
💡 Suggestion
Tab
to accept
Esc
to dismiss
// Output will appear here after running code