Watch 10 video solutions for Sqrt(x), a easy level problem involving Math, Binary Search. This walkthrough by take U forward has 188,538 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 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.
| 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 |