Sqrt(x)
EasyPrompt
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.
- For example, do not use
pow(x, 0.5)in c++ orx ** 0.5in 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 - 1
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves iterating through numbers starting from 1 and checking if their square is equal to or just exceeds the input x. The integer square root is the largest integer i for which i*i <= x.
Algorithm
- Handle the edge case where
xis 0. Ifxis 0, the square root is 0. - Initialize a loop counter
ito 1. Use alongforito prevent overflow during multiplication. - In each iteration, check if
i * i > x. - If this condition is met, it means
(i-1)*(i-1) <= xandi*i > x. Therefore,i-1is the answer. Return(int)(i-1). - If
i * i == x, theniis the perfect square root, return(int)i. - The loop will eventually terminate because for a large enough
i,i*iwill exceedx.
Walkthrough
We can iterate with a variable i from 1 upwards. For each i, we compute its square. To avoid integer overflow when calculating i*i for large i, it's crucial to use a larger data type, like long in Java. The loop continues as long as i*i <= x. When the loop finds an i such that i*i > x, the previous integer, i-1, must be the integer square root of x.
class Solution { public int mySqrt(int x) { if (x == 0) { return 0; } for (long i = 1; i <= x; i++) { if (i * i > x) { return (int) (i - 1); } if (i * i == x) { return (int) i; } } return -1; // Should not be reached for non-negative x }}Complexity
Time
O(sqrt(x))
Space
O(1)
Trade-offs
Pros
Simple to understand and implement.
Cons
Inefficient for large values of
x. It can lead to a "Time Limit Exceeded" error on online judges.
A more efficient method is to use binary search. The problem is to find an integer k in the sorted range [0, x] such that k*k <= x < (k+1)*(k+1). The function f(k) = k*k is monotonic, making binary search applicable.
Algorithm
- Handle edge cases: if
xis 0 or 1, returnx. - Initialize
left = 1andright = x. These define our search space. - Loop as long as
left <= right. - In each iteration, calculate the middle element
mid = left + (right - left) / 2. - To prevent overflow, cast
midtolongbefore squaring:long square = (long) mid * mid;. - If
square > x, the answer lies in the left half. Setright = mid - 1. - If
square <= x,midis a potential answer. We store it and continue searching for a larger potential answer in the right half. Setleft = mid + 1. - When the loop terminates (
left > right), the stored result is the answer. An alternative is thatrightwill hold the largest integer whose square is less than or equal tox.
Walkthrough
We are searching for the square root within the range of integers from 0 to x. We can apply binary search on this range. For any chosen number mid, if mid*mid > x, we know the actual square root must be smaller than mid, so we search in the left half. If mid*mid <= x, mid could be our answer, but there might be a larger integer whose square is also less than or equal to x, so we search in the right half.
class Solution { public int mySqrt(int x) { if (x < 2) { return x; } long left = 1, right = x; int result = 0; while (left <= right) { long mid = left + (right - left) / 2; long midSquared = mid * mid; if (midSquared == x) { return (int) mid; } else if (midSquared < x) { // mid could be the answer, try for a larger one result = (int) mid; left = mid + 1; } else { // midSquared > x // mid is too large right = mid - 1; } } return result; }}Complexity
Time
O(log x)
Space
O(1)
Trade-offs
Pros
Significantly faster than linear search.
Guaranteed to find the solution within the time limits for the given constraints.
Cons
Slightly more complex to implement than the brute-force approach.
Newton's method is a very fast numerical technique for finding successively better approximations to the roots of a function. To find sqrt(x), we seek the root of the function f(y) = y^2 - x.
Algorithm
- Handle the edge case
x = 0. - Initialize the guess
ras alongwith the value ofx. - Loop as long as
r * r > x. - In each iteration, update the guess using the formula:
r = (r + x / r) / 2. - The loop terminates when
r*r <= x. At this point,ris the integer part of the square root. - Return
rcast to anint.
Walkthrough
The iterative formula for Newton's method is y_{n+1} = y_n - f(y_n) / f'(y_n). For our function f(y) = y^2 - x, the derivative is f'(y) = 2y. Substituting these into the formula gives the recurrence relation: y_{n+1} = (y_n + x / y_n) / 2. We can start with an initial guess, for example y_0 = x, and iterate until the result converges. Since we are working with integers, the process will converge very quickly. The loop can terminate when our guess y squared is no longer greater than x.
class Solution { public int mySqrt(int x) { if (x == 0) { return 0; } long r = x; while (r * r > x) { r = (r + x / r) / 2; } return (int) r; }}Complexity
Time
O(log x)
Space
O(1)
Trade-offs
Pros
Extremely fast, often the fastest method in practice.
Elegant and concise implementation.
Cons
The mathematical concept might be less intuitive than binary search for some.
Requires careful handling of integer division and potential overflows (using
longhelps).
Solutions
Solution
public class Solution { public int MySqrt ( int x ) { int l = 0 , r = x ; while ( l < r ) { int mid = ( l + r + 1 ) >>> 1 ; if ( mid > x / mid ) { r = mid - 1 ; } else { l = mid ; } } return l ; } }class Solution {public int mySqrt(int x) { int l = 0, r = x; while (l < r) { int mid = (l + r + 1) >>> 1; if (mid > x / mid) { r = mid - 1; } else { l = mid; } } return l; }}/** * @param {number} x * @return {number} */ var mySqrt = function (x) { let [l, r] = [0, x]; while (l < r) { const mid = (l + r + 1) >> 1; if (mid > x / mid) { r = mid - 1; } else { l = mid; } } return l;};class Solution {public: int mySqrt(int x) { int l = 0, r = x; while (l < r) { int mid = (l + r + 1ll) >> 1; if (mid > x / mid) { r = mid - 1; } else { l = mid; } } return l; }};class Solution: def mySqrt(self, x: int) -> int: l, r = 0, x while l < r: mid = (l + r + 1) >> 1 if mid > x // mid: r = mid - 1 else: l = mid return lVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.