Watch 10 video solutions for Sqrt(x), a easy level problem involving Math, Binary Search. This walkthrough by NeetCodeIO has 123,958 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
pow(x, 0.5) in c++ or x ** 0.5 in python.
Example 1:
Input: x = 4 Output: 2 Explanation: The square root of 4 is 2, so we return 2.
Example 2:
Input: x = 8 Output: 2 Explanation: The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned.
Constraints:
0 <= x <= 231 - 1Problem Overview: Given a non‑negative integer x, compute and return the integer square root of x. The result must be truncated to the nearest integer (floor value). You cannot use built‑in exponent or square root functions.
Approach 1: Linear Iteration (O(sqrt(n)) time, O(1) space)
The simplest idea is to try every integer starting from 1 and stop when i * i becomes greater than x. The last valid i where i * i ≤ x is the answer. This approach directly models the mathematical definition of square root. However, it performs up to sqrt(x) iterations, which becomes slow for large inputs such as x = 2^31 - 1. This version is useful for understanding the problem before moving to logarithmic solutions.
Approach 2: Binary Search (O(log n) time, O(1) space)
The square root function is monotonic: as i increases, i * i also increases. That means you can search the answer using binary search. Define a search range from 1 to x. Compute mid, then compare mid * mid with x. If it's equal, return mid. If it's smaller, move the left boundary to search for a larger value. If it's larger, shrink the right boundary. The final answer is the largest mid where mid * mid ≤ x. This reduces the search space by half each step, giving O(log x) time. The approach relies purely on arithmetic and is a common application of math reasoning combined with binary search.
Approach 3: Newton's Method (O(log n) time, O(1) space)
Newton's Method (also called Newton–Raphson) uses numerical optimization to approximate square roots. Start with an initial guess r = x. Repeatedly update the estimate using r = (r + x / r) / 2. Each iteration moves the estimate closer to the true square root. Stop when r * r ≤ x. This method converges extremely fast, usually within a few iterations even for large numbers. It’s widely used in numerical computing and demonstrates deeper mathematical insight compared to brute approaches.
Recommended for interviews: Binary Search is the most expected solution. It shows you recognize the monotonic property and can apply logarithmic search correctly. The linear scan demonstrates basic reasoning but lacks efficiency. Newton's Method is impressive if you know it, though many interviewers are perfectly satisfied with the binary search solution.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Linear Iteration | O(sqrt(n)) | O(1) | Good for conceptual understanding or very small inputs |
| Binary Search | O(log n) | O(1) | Standard interview solution using monotonic search space |
| Newton's Method | O(log n) | O(1) | When fast numerical convergence or mathematical optimization is preferred |