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.
This approach uses binary search to find the integer square root of the given number x. The idea is to use a binary search over the range [0, x] to find the largest number whose square is less than or equal to x. The time complexity of this approach is logarithmic, which makes it very efficient.
This implementation uses binary search. The mySqrt function initializes two pointers, left and right, to define the search space. The mid-point is calculated, and the square of the mid-point is compared with x. The search space is adjusted accordingly until it converges.
Time Complexity: O(log x)
Space Complexity: O(1)
Newton's Method (also known as the Newton-Raphson method) can also be applied to find the square root of a number through iteration. The general formula for updating a guess g is g = (g + x/g) / 2. This keeps refining the guess based on how close it is to x/g.
This implementation uses Newton's method to find the square root. It initializes g as the guess, and iteratively updates g until g * g is sufficiently close to x.
Time Complexity: O(log x)
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Binary Search | Time Complexity: O(log x) |
| Newton's Method | Time Complexity: O(log x) |
| 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 |
Sqrt(x) - Leetcode 69 - Python • NeetCodeIO • 123,958 views views
Watch 9 more video solutions →Practice Sqrt(x) with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor