0069. Sqrt(x)¶

Table of Contents¶

1. Problem
2. Problem Breakdown
3. Approach 1: Linear Search (Brute Force)
4. Approach 2: Binary Search
5. Approach 3: Newton's Method
6. Approach 4: Bit Manipulation (Digit-by-Digit)
7. Complexity Comparison
8. Edge Cases
9. Common Mistakes
10. Related Problems
11. Visual Animation

Problem¶

Leetcode	69. Sqrt(x)
Difficulty	Easy
Tags	Math, Binary Search

Description¶

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++ or `x ** 0.5` in python.

Examples¶

Example 1:
Input: x = 4
Output: 2

Example 2:
Input: x = 8
Output: 2
Explanation: floor(sqrt(8)) = floor(2.828...) = 2.

Constraints¶

• 0 <= x <= 2^31 - 1

Problem Breakdown¶

1. What is being asked?¶

Find floor(sqrt(x)) -- the largest integer r such that r * r <= x.

2. What is the input?¶

3. What is the output?¶

A single non-negative integer: the floor of the real square root.

4. Constraints analysis¶

5. Step-by-step example analysis¶

x = 8¶

Binary search on [0, 8]:
  lo = 0, hi = 8
  mid = 4: 4*4 = 16 > 8 → hi = 3
  lo = 0, hi = 3, mid = 1: 1 ≤ 8 → ans = 1, lo = 2
  lo = 2, hi = 3, mid = 2: 4 ≤ 8 → ans = 2, lo = 3
  lo = 3, hi = 3, mid = 3: 9 > 8 → hi = 2
  loop ends.
Return ans = 2.

6. Key Observations¶

1. Monotonic search space -- r * r is monotonically non-decreasing in r. Binary search is the natural fit.
2. Newton's method converges quadratically -- Iterate r = (r + x / r) / 2 until convergence. Very few iterations.
3. Bit manipulation per-digit method -- Compute the integer square root one bit at a time. Very efficient and overflow-safe.
4. Overflow -- Avoid mid * mid for very large x; use x / mid or long.

7. Pattern identification¶

Chosen pattern: Binary Search for clarity, Newton's for speed.

Approach 1: Linear Search (Brute Force)¶

Idea¶

Increment r from 0 until (r+1)^2 > x. The current r is the answer.

Complexity¶

O(46341) at worst — fast in absolute terms, but O(log x) is far better.

Implementation¶

Python¶

class Solution:
    def mySqrtLinear(self, x: int) -> int:
        r = 0
        while (r + 1) * (r + 1) <= x:
            r += 1
        return r

Approach 2: Binary Search¶

Algorithm (step-by-step)¶

1. If x < 2, return x.
2. lo = 1, hi = x // 2, ans = 0.
3. While lo <= hi:
4. mid = (lo + hi) // 2.
5. If mid * mid <= x: ans = mid, lo = mid + 1.
6. Else: hi = mid - 1.
7. Return ans.

Complexity¶

Implementation¶

Go¶

func mySqrt(x int) int {
    if x < 2 {
        return x
    }
    lo, hi := 1, x/2
    ans := 0
    for lo <= hi {
        mid := (lo + hi) / 2
        if mid <= x/mid {
            ans = mid
            lo = mid + 1
        } else {
            hi = mid - 1
        }
    }
    return ans
}

Comparing mid <= x/mid instead of mid*mid <= x avoids overflow in 32-bit.

Java¶

class Solution {
    public int mySqrt(int x) {
        if (x < 2) return x;
        int lo = 1, hi = x / 2, ans = 0;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            // Use long to avoid overflow when mid * mid is computed
            if ((long) mid * mid <= x) {
                ans = mid;
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return ans;
    }
}

Python¶

class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2: return x
        lo, hi, ans = 1, x // 2, 0
        while lo <= hi:
            mid = (lo + hi) // 2
            if mid * mid <= x:
                ans = mid
                lo = mid + 1
            else:
                hi = mid - 1
        return ans

Dry Run¶

x = 8
lo=1, hi=4, ans=0
mid=2: 4 ≤ 8 → ans=2, lo=3
mid=3: 9 > 8 → hi=2
lo>hi → return 2

Approach 3: Newton's Method¶

Idea¶

The iteration r := (r + x/r) / 2 converges quadratically to sqrt(x).

Start with r = x (or x // 2 for speed). Iterate until r * r <= x. Then r is the floor of the true square root.

Algorithm (step-by-step)¶

1. If x < 2, return x.
2. r = x.
3. While r * r > x: r = (r + x // r) // 2.
4. Return r.

Complexity¶

Implementation¶

Python¶

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

Go¶

func mySqrtNewton(x int) int {
    if x < 2 {
        return x
    }
    r := x
    for r*r > x {
        r = (r + x/r) / 2
    }
    return r
}

Java¶

class Solution {
    public int mySqrtNewton(int x) {
        if (x < 2) return x;
        long r = x;
        while (r * r > x) {
            r = (r + x / r) / 2;
        }
        return (int) r;
    }
}

Dry Run¶

x = 16
r = 16, 16*16 = 256 > 16 → r = (16 + 1) / 2 = 8
r = 8, 64 > 16 → r = (8 + 2) / 2 = 5
r = 5, 25 > 16 → r = (5 + 3) / 2 = 4
r = 4, 16 ≤ 16 → return 4

Approach 4: Bit Manipulation (Digit-by-Digit)¶

Idea¶

Compute the square root by determining each bit from the highest to the lowest. For each candidate bit set in r, check whether the new r * r <= x. Equivalent to integer Newton with subtraction-only arithmetic.

Useful when multiplication is expensive or you want a hardware-style algorithm.

Implementation¶

Python¶

class Solution:
    def mySqrtBits(self, x: int) -> int:
        if x < 2: return x
        result = 0
        bit = 1 << 16   # max useful bit for x <= 2^31 - 1 (since sqrt < 2^16)
        while bit > 0:
            cand = result | bit
            if cand * cand <= x:
                result = cand
            bit >>= 1
        return result

Complexity Comparison¶

Which solution to choose?¶

• In an interview: Approach 2 (binary search) — clearest
• In production: Approach 2 or 3
• On Leetcode: Either passes

Edge Cases¶

Common Mistakes¶

Mistake 1: Integer overflow with mid * mid¶

// WRONG — int * int overflows
int mid = (lo + hi) / 2;
if (mid * mid <= x) ...

// CORRECT — cast or use division
if ((long) mid * mid <= x) ...
// or
if (mid <= x / mid) ...

Reason: For x near 2^31, mid can be ~46340 and mid * mid ~2.1 * 10^9, which fits but is risky.

Mistake 2: Initial Newton seed of 0¶

# WRONG — division by zero on the very first iteration
r = 0
while r * r > x:
    r = (r + x // r) // 2

# CORRECT
r = x

Reason: Newton needs a positive seed.

Mistake 3: Forgetting x < 2 shortcut¶

# WRONG — for x == 0, x // 2 == 0, and binary search loop never executes (lo=1, hi=0), returns ans=0 — actually fine
# But for the Newton method, r = 0 trips division

Reason: Always handle x = 0 and x = 1 first.

Related Problems¶

#	Problem	Difficulty	Similarity
1	50. Pow(x, n)	Medium	Reverse: power instead of root
2	367. Valid Perfect Square	Easy	Same algorithm, equality check
3	704. Binary Search	Easy	Pure binary search practice

Visual Animation¶

Interactive animation: animation.html

The animation includes: - Number line with current lo, hi, mid markers - Live mid * mid evaluation - Newton-method tab showing the iteration r := (r + x/r) / 2 - Adjustable input x slider