Sqrt(x)

Difficulty: Easy | Acceptance: 41.80% | Paid: No Topics: Math, Binary Search

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. Return the integer part of the square root of x. Note that you are not allowed to use any built-in exponent function or operator, such as pow(x, 0.5) or x ** 0.5.

• Examples
• Constraints
• Approach 1: Linear Search
• Approach 2: Binary Search
• Approach 3: Newton’s Method

Examples

Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 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 <= 2³¹ - 1

Approach 1: Linear Search

Intuition We can iterate through all integers from 0 to x and check if the square of the integer is equal to x. The first integer whose square exceeds x indicates that the previous integer is the floor of the square root.

Steps

• Handle the edge case where x is 0 or 1.
• Iterate from 1 to x.
• If i * i equals x, return i.
• If i * i exceeds x, return i - 1.

class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x
        i = 1
        while i * i <= x:
            if i * i == x:
                return i
            i += 1
        return i - 1

Complexity

• Time: O(√x) — In the worst case, we iterate up to the square root of x.
• Space: O(1) — We only use a single variable for iteration.
• Notes: This approach is simple but inefficient for very large values of x (e.g., close to 2³¹).

Approach 2: Binary Search

Intuition The square root of x lies between 0 and x. Since the sequence of squares is sorted, we can use binary search to efficiently find the largest integer mid such that mid² ≤ x.

Steps

• Initialize left = 0 and right = x.
• While left ≤ right:
  • Calculate mid = left + (right - left) / 2.
  • Calculate square = mid * mid.
  • If square == x, return mid.
  • If square < x, move left to mid + 1 (search for a potentially larger root).
  • If square > x, move right to mid - 1 (search for a smaller root).
• When the loop ends, right is the largest integer satisfying right² ≤ x.

class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x
        left, right = 1, x // 2
        while left <= right:
            mid = left + (right - left) // 2
            sq = mid * mid
            if sq == x:
                return mid
            elif sq < x:
                left = mid + 1
            else:
                right = mid - 1
        return right

Complexity

• Time: O(log x) — We halve the search space in each iteration.
• Space: O(1) — Only a few integer variables are used.
• Notes: Care must be taken with integer overflow when calculating mid * mid. Using long (Java/C++) or ensuring the logic handles large numbers is necessary.

Approach 3: Newton’s Method

Intuition Newton’s Method (also known as the Heron’s method) is an efficient algorithm for finding successively better approximations to the roots (or zeroes) of a real-valued function. For finding √x, we solve r² - x = 0. The iterative formula is r_(n+1) = (r_n + x / r_n) / 2.

Steps

• If x is 0 or 1, return x.
• Initialize r = x.
• While r * r > x:
  • Update r to the average of r and x / r.
• Return r (cast to integer).

class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x
        r = x
        while r * r > x:
            r = (r + x // r) // 2
        return r

Complexity

• Time: O(log x) — The number of correct digits roughly doubles with each step, leading to logarithmic convergence.
• Space: O(1) — Constant space usage.
• Notes: This is often faster than binary search in practice due to the quadratic convergence rate, though it involves division which can be computationally expensive on some hardware.