LeetCode 69: Sqrt(x) Solution in Python Explained

Problem Statement

LeetCode 69, Sqrt(x), is an easy-level problem where you’re given a non-negative integer x. Your task is to compute and return the integer square root of x, i.e., the largest integer whose square is less than or equal to x (floor of (\sqrt{x})). You cannot use built-in square root functions like math.sqrt().

Constraints

0 <= x <= 2^31 - 1: Input is a 32-bit non-negative integer.

Example

Input: x = 4
Output: 2
Explanation: 2^2 = 4 ≤ 4, 3^2 = 9 > 4, so sqrt(4) = 2.

Input: x = 8
Output: 2
Explanation: 2^2 = 4 ≤ 8, 3^2 = 9 > 8, so sqrt(8) = 2 (floor).

Input: x = 0
Output: 0
Explanation: 0^2 = 0, sqrt(0) = 0.

Understanding the Problem

How do you solve LeetCode 69: Sqrt(x) in Python? For x = 8, find the largest integer whose square is ≤ 8—here, it’s 2 since (2^2 = 4 \leq 8) and (3^2 = 9 > 8). We need an efficient method to compute this without built-in functions. We’ll explore two approaches: a Binary Search Solution (optimal and primary) and an Alternative with Newton’s Method (fast and mathematical). The binary search method runs in O(log x) time with O(1) space, leveraging the sorted nature of squares.

Solution 1: Binary Search Approach (Primary)

Explanation

Use binary search to find the largest integer (mid) such that (mid^2 \leq x). Since (x) is non-negative, search from 0 to (x) (or a smaller upper bound like (\min(x, 46340)) to avoid overflow), adjusting the range based on whether (mid^2) is less than, equal to, or greater than (x).

Here’s a flow for (x = 8):

Range: [0, 8]
mid = 4, 4^2 = 16 > 8, right = 3
mid = 2, 2^2 = 4 ≤ 8, left = 3
mid = 3, 3^2 = 9 > 8, right = 2
left > right, return 2

Handle Edge Cases.

If \(x = 0\) or \(1\), return \(x\).

Binary Search.

Set left = 1, right = \(x\), find largest \(mid\) where \(mid^2 \leq x\).

Adjust Range.

If \(mid^2 > x\), move right; if \(mid^2 \leq x\), move left.

Return Result.

Largest \(mid\) satisfying condition.

Step-by-Step Example

Example 1: x = 8

We need 2.

Goal: Find integer sqrt of 8.
Result for Reference: 2.
Start: x = 8, left = 1, right = 8.
Step 1: mid = (1 + 8) // 2 = 4.

\(4^2 = 16 > 8\), right = 3.

Step 2: mid = (1 + 3) // 2 = 2.

\(2^2 = 4 \leq 8\), left = 3.

Step 3: mid = (3 + 3) // 2 = 3.

\(3^2 = 9 > 8\), right = 2.

Step 4: left = 3 > right = 2, stop.
Finish: Return right = 2 (largest \(mid\) where \(mid^2 \leq 8\)).

Example 2: x = 4

We need 2.

Start: left = 1, right = 4.
Step 1: mid = 2.

\(2^2 = 4 \leq 4\), left = 3.

Step 2: mid = 3.

\(3^2 = 9 > 4\), right = 2.

Step 3: left = 3 > right = 2, stop.
Finish: Return 2.

How the Code Works (Binary Search)

Here’s the Python code with line-by-line explanation:

def mySqrt(x: int) -> int:
    # Line 1: Handle edge cases
    if x <= 1:
        return x

    # Line 2: Initialize binary search range
    left, right = 1, x

    # Line 3: Binary search for sqrt
    while left <= right:
        mid = (left + right) // 2
        square = mid * mid
        # Line 4: Adjust range based on square
        if square == x:
            return mid
        elif square > x:
            right = mid - 1
        else:
            left = mid + 1

    # Line 5: Return largest integer sqrt
    return right

Alternative: Newton’s Method Approach

Explanation

Use Newton’s method to iteratively approximate (\sqrt{x}). Start with an initial guess (e.g., (x)), refine it using the formula (guess = (guess + x / guess) / 2), and stop when (guess^2 \leq x) but ((guess+1)^2 > x). This converges quadratically, making it very fast.

Here’s a flow for (x = 8):

guess = 8
guess = (8 + 8/8) / 2 = 4.5
guess = (4.5 + 8/4.5) / 2 ≈ 3.14
guess = (3.14 + 8/3.14) / 2 ≈ 2.84
guess ≈ 2 after floor, 2^2 ≤ 8, 3^2 > 8

Initial Guess.

Start with \(x\).

Iterate Newton’s Formula.

Refine guess until it stabilizes.

Floor Result.

Take largest integer satisfying condition.

Return Result.

Step-by-Step Example (Alternative)

For (x = 8):

Start: guess = 8.
Step 1: guess = (8 + 8/8) / 2 = 4.5.
Step 2: guess = (4.5 + 8/4.5) / 2 ≈ 3.14.
Step 3: guess = (3.14 + 8/3.14) / 2 ≈ 2.84.
Step 4: guess = (2.84 + 8/2.84) / 2 ≈ 2.82, floor = 2.
Step 5: \(2^2 = 4 \leq 8\), \(3^2 = 9 > 8\), stop.
Finish: Return 2.

How the Code Works (Newton’s Method)

def mySqrtNewton(x: int) -> int:
    # Line 1: Handle edge cases
    if x <= 1:
        return x

    # Line 2: Initial guess
    guess = x

    # Line 3: Newton’s iteration
    while guess * guess > x:
        guess = (guess + x // guess) // 2

    # Line 4: Return integer sqrt
    return guess

Complexity

Binary Search:

Time: O(log x) – Binary search halves range.
Space: O(1) – Only variables.

Newton’s Method:

Time: O(log log x) – Quadratic convergence (approximate).
Space: O(1) – Only guess variable.

Efficiency Notes

Binary Search is O(log x) time and O(1) space, reliable and optimal for LeetCode 69 within constraints. Newton’s Method is theoretically faster (O(log log x)) due to quadratic convergence, also O(1) space, but may be less intuitive and slightly less predictable in practice.

Key Insights

Tips to master LeetCode 69:

Binary Search: Find largest \(mid\) where \(mid^2 \leq x\).
Newton’s Speed: Use iterative refinement for fast convergence.
Overflow Caution: Handle large \(x\) without exceeding limits.

Additional Example

For (x = 16):

Goal: 4.
Binary: [1,16] -> mid=8 (64>16) -> [1,7] -> mid=4 (16=16), return 4.
Newton: guess=16 -> 8.5 -> 4.2 -> 4, return 4.
Result: 4.

Edge Cases

\(x = 0\): Return 0.
\(x = 1\): Return 1.
Large \(x\): \(2^{31}-1\), binary search or Newton’s handles efficiently.

Final Thoughts

The Binary Search solution is a dependable choice for LeetCode 69 in Python—clear, efficient, and precise, with Newton’s Method offering a fast alternative. For a related challenge, try LeetCode 68: Text Justification to switch gears! Ready to root it out? Solve LeetCode 69 on LeetCode now and test it with 8 or 16 to master square roots. Dive in and find the floor!