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 should be the floor of the real square root, meaning you return the largest integer r such that r * r ≤ x. Built‑in square root functions are not allowed.
Approach 1: Linear Scan (O(√x) time, O(1) space)
The most direct idea is to iterate integers starting from 1 and keep checking i * i until the value exceeds x. The previous number is the integer square root. This approach works because the square root of x cannot exceed √x, so the loop stops around that point. The downside is performance: when x is large, iterating up to √x becomes expensive. This brute force strategy demonstrates the problem constraints clearly but rarely passes strict performance expectations in interviews.
Approach 2: Binary Search (O(log x) time, O(1) space)
The integer square root lies between 0 and x. This monotonic property makes the problem a natural fit for binary search. Pick a midpoint mid, compute mid * mid, and compare it with x. If the square is too large, search the left half; otherwise move right while tracking the last valid candidate. This halves the search range each iteration, giving O(log x) time complexity. Careful handling of overflow (using division like mid ≤ x / mid) keeps the implementation safe for large integers. This is the most common interview solution.
Approach 3: Newton's Method (O(log x) time, O(1) space)
Newton's Method uses iterative approximation from numerical math. Start with a guess r = x. Update the guess using the formula r = (r + x / r) / 2. Each iteration rapidly converges toward the true square root because the formula reduces the error quadratically. Continue until r * r ≤ x. This approach often converges faster than binary search in practice and is widely used in numerical computing. The tradeoff is that the reasoning is less intuitive compared to the straightforward binary search approach.
Recommended for interviews: Binary Search is the expected answer. It shows you recognize the monotonic relationship between n and n² and can apply logarithmic search correctly. Mentioning the linear scan first shows baseline reasoning, but implementing binary search demonstrates stronger algorithmic thinking. Newton's Method is a good bonus discussion if the interviewer asks for alternative mathematical optimizations.
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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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 Scan | O(√x) | O(1) | Simple brute force explanation or very small inputs |
| Binary Search | O(log x) | O(1) | Most common interview solution for monotonic search space |
| Newton's Method | O(log x) | O(1) | When using mathematical approximation for faster convergence |
BS-10. Finding Sqrt of a number using Binary Search • take U forward • 188,538 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