56. Sqrt(x)

🔗 LeetCode Problem: 69. Sqrt(x)
📊 Difficulty: Easy
🏷️ Topics: Math, Binary Search

Problem Statement

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.

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 <= 2^31 - 1

🎨 Visual Understanding

The Problem Visualized

Find: floor(√x)

x = 8

√8 = 2.82842...
     ↓ (round down)
Answer: 2

Visual representation:
0  1  2  3  4  5  6  7  8  9
         ↑
      Answer: 2

2² = 4 ≤ 8 ✓
3² = 9 > 8  ✗

So 2 is the largest integer whose square ≤ 8

x = 16

√16 = 4.0 (exact)
Answer: 4

0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16
            ↑
         Answer: 4

4² = 16 ≤ 16 ✓
5² = 25 > 16 ✗

🚨 CRITICAL INSIGHT - Why Binary Search Works

The Key Pattern!

We're searching for the largest integer k such that k² ≤ x

Think of it as searching in this sequence:
  Numbers:  0  1  2  3  4  5  6  7  8  9  10
  Squares:  0  1  4  9  16 25 36 49 64 81 100

For x = 8:
  Which numbers have square ≤ 8?
  0² = 0  ≤ 8 ✓
  1² = 1  ≤ 8 ✓
  2² = 4  ≤ 8 ✓
  3² = 9  > 8 ✗
  4² = 16 > 8 ✗
  ...

Pattern: [✓ ✓ ✓ | ✗ ✗ ✗ ...]
         [YYYYYYYY | NNNNNN ...]

We need the LAST ✓ (largest valid)
= Find rightmost position where square ≤ x
= Binary Search on Answer Space!

Why This is Binary Search on Answer Space

Search Space:
  Not searching in an array
  Searching range [0, x] for answer

  Each "candidate" is a potential sqrt
  Each candidate has a property: square ≤ x or square > x

The Goal:
  Find LARGEST number whose square ≤ x
  = Find rightmost valid position
  = "Find Last/Upper Bound" pattern!

Key Insight:
  If k² ≤ x, then answer is k or larger
  If k² > x, then answer is smaller than k

  Can eliminate half at each step!

Example: x = 8, range [0, 8]

Check mid = 4:
  4² = 16 > 8
  Answer must be < 4
  Search [0, 3]

Check mid = 1:
  1² = 1 ≤ 8
  Answer could be 1 or larger
  Search [2, 3]

Check mid = 2:
  2² = 4 ≤ 8
  Answer could be 2 or larger
  Search [3, 3]

Check mid = 3:
  3² = 9 > 8
  Answer must be < 3
  Search ends

Best found: 2 ✓

The Binary Search Invariant

Throughout the search:
  All numbers with square ≤ x are in [left, result]
  All numbers with square > x are in [result+1, right]

We track the best valid answer found so far:
  When mid² ≤ x: update result = mid, search right
  When mid² > x: search left

After loop: result = largest number whose square ≤ x

🎯 Approach 1: Linear Search (Brute Force)

The Most Natural Thinking 💭

Core Logic:

Start from 0 and check each number:
  If i² ≤ x and (i+1)² > x, then i is the answer

Or simply: find largest i where i² ≤ x

Implementation

public int mySqrt(int x) {
    if (x < 2) return x;  // 0 and 1 are special cases

    // Check each number from 0 to x
    for (int i = 0; i <= x; i++) {
        long square = (long) i * i;  // Use long to avoid overflow

        // If current square exceeds x, previous was answer
        if (square > x) {
            return i - 1;
        }

        // If exact match
        if (square == x) {
            return i;
        }
    }

    return x;  // Should never reach here
}

⏰ Time: O(√x) - Check up to √x numbers
💾 Space: O(1) - Only variables

Why This Works:

We increment i until i² > x
Then i-1 is the largest number whose square ≤ x

❌ Problem: Too slow for large x! If x = 2^31-1, checking billions of numbers!

🎯 Approach 2: Binary Search (Optimal) ⭐

Better Approach 💡

🧠 The Core Insight

The answer is in range [0, x]
We're looking for: largest k where k² ≤ x

This is MONOTONIC:
  If k² ≤ x, then (k-1)² also ≤ x
  If k² > x, then (k+1)² also > x

Pattern: [valid valid valid ... valid | invalid invalid ...]
         [YYYYYYYYYYYYYYYYYYYY | NNNNNNNNNNNNN]

Find the LAST valid (rightmost Y)
= Binary Search on Answer Space!

The Strategy:

Binary search on range [0, x]:
  If mid² ≤ x:
    mid is valid, might be answer
    But there might be larger valid number
    Track mid as potential answer
    Search right half

  If mid² > x:
    mid is too large
    Search left half

After loop: return best valid number found

Implementation

public int mySqrt(int x) {
    // Edge cases
    if (x < 2) return x;  // sqrt(0) = 0, sqrt(1) = 1

    int left = 0;
    int right = x;
    int result = 0;  // Track best valid answer

    while (left <= right) {
        // Safe mid calculation
        int mid = left + (right - left) / 2;

        // Use long to avoid overflow when calculating mid * mid
        long square = (long) mid * mid;

        if (square == x) {
            // Exact square root found
            return mid;
        }

        if (square < x) {
            // mid is valid, but there might be larger valid number
            result = mid;  // Track this as potential answer
            left = mid + 1;  // Search for larger
        } else {
            // mid is too large
            right = mid - 1;  // Search for smaller
        }
    }

    return result;  // Best valid answer found
}

⏰ Time: O(log x) - Binary search
💾 Space: O(1) - Only variables

🔍 Dry Run

Example 1: x = 8

Goal: Find largest k where k² ≤ 8

Initial: left = 0, right = 8, result = 0
         [0, 1, 2, 3, 4, 5, 6, 7, 8]
          ↑                       ↑
        left                    right

Iteration 1:
  mid = 0 + (8 - 0) / 2 = 4
  square = 4 × 4 = 16
  16 > 8, too large
  right = 3
  [0, 1, 2, 3, 4, 5, 6, 7, 8]
   ↑        ↑
  left    right

Iteration 2:
  mid = 0 + (3 - 0) / 2 = 1
  square = 1 × 1 = 1
  1 ≤ 8, valid!
  result = 1 (track it)
  left = 2
  [0, 1, 2, 3, 4, 5, 6, 7, 8]
         ↑  ↑
       left right

Iteration 3:
  mid = 2 + (3 - 2) / 2 = 2
  square = 2 × 2 = 4
  4 ≤ 8, valid!
  result = 2 (better answer)
  left = 3
  [0, 1, 2, 3, 4, 5, 6, 7, 8]
            ↑
         left/right

Iteration 4:
  mid = 3 + (3 - 3) / 2 = 3
  square = 3 × 3 = 9
  9 > 8, too large
  right = 2
  [0, 1, 2, 3, 4, 5, 6, 7, 8]
         ↑  ↑
      right left

Loop ends (left > right)
return result = 2 ✓

Verification: 2² = 4 ≤ 8, 3² = 9 > 8 ✓

Example 2: x = 4

Goal: Find largest k where k² ≤ 4

Initial: left = 0, right = 4, result = 0
         [0, 1, 2, 3, 4]
          ↑           ↑
        left        right

Iteration 1:
  mid = 0 + (4 - 0) / 2 = 2
  square = 2 × 2 = 4
  4 == 4, exact match!
  return 2 ✓

Verification: √4 = 2 exactly ✓

Example 3: x = 0

Edge case: x < 2
return x = 0 ✓

Example 4: x = 1

Edge case: x < 2
return x = 1 ✓

Example 5: x = 2147395599 (large number)

Initial: left = 0, right = 2147395599

After ~31 binary search iterations:
  Finds answer = 46339

Verification: 46339² = 2147395521 ≤ 2147395599 ✓
              46340² = 2147488400 > 2147395599 ✓

Without long cast:
  46340 × 46340 would overflow!
  That's why we use (long) mid * mid

🎯 Why This Works - Deep Dive

The Search Space:
═══════════════════════════════════════════════════════════════

Range: [0, x]
But can we optimize?

For x > 1, √x < x/2
So we can search [0, x/2]... but x/2 still large

For safety and simplicity, search [0, x]
Binary search is fast enough!

The result Variable:
═══════════════════════════════════════════════════════════════

Why track result separately?
  When mid² ≤ x, mid is VALID
  But there might be LARGER valid number

  So we:
    1. Save mid as potential answer (result = mid)
    2. Keep searching right (left = mid + 1)

  If we find larger valid, we update result
  If all larger numbers are invalid, result has answer!

This is "Find Last Valid" pattern:
  Keep tracking best valid found
  Keep searching for better

Overflow Prevention:
═══════════════════════════════════════════════════════════════

Critical: long square = (long) mid * mid

Why?
  mid can be up to x ≈ 2^31
  mid × mid can overflow int range

Example:
  mid = 46341
  mid × mid = 2,147,488,281
  As int: OVERFLOW (wraps to negative!)
  As long: Correct positive value ✓

Always cast to long BEFORE multiplication!

Why Not Check mid > x/mid?
═══════════════════════════════════════════════════════════════

Alternative to avoid overflow:
  Instead of: mid × mid > x
  Check: mid > x / mid

This works but:
  - Division is slower than multiplication
  - Needs special handling when mid = 0
  - Less clear code

Using long cast is cleaner and fast enough!

The "Find Last Valid" Pattern

This is the template for finding LAST/LARGEST valid:

1. Track result variable (best found so far)
2. When condition is TRUE:
   result = mid (track it)
   left = mid + 1 (search for better)
3. When condition is FALSE:
   right = mid - 1 (search smaller)
4. Return: result after loop

Applies to:
  - Find largest number with property
  - Find rightmost valid position
  - Find floor/maximum under constraint

Key insight:
  result preserves best answer found
  Continue searching for better

⚠️ Common Mistakes to Avoid

Mistake 1: Not using long for square

// ❌ WRONG - Integer overflow
int square = mid * mid;
if (square > x) { ... }

// ✓ CORRECT - Use long
long square = (long) mid * mid;
if (square > x) { ... }

Why it's critical:

For x = 2147395599, mid = 46341
mid * mid as int: OVERFLOW (negative number!)
Comparison breaks completely!

Cast to long BEFORE multiplication:
(long) mid * mid = correct positive value ✓

Mistake 2: Not tracking result

// ❌ WRONG - Might return wrong answer
while (left <= right) {
    if (mid * mid <= x) {
        left = mid + 1;  // Lost the valid mid!
    }
}
return left;  // Wrong!

// ✓ CORRECT - Track result
int result = 0;
while (left <= right) {
    if (square <= x) {
        result = mid;  // Save it!
        left = mid + 1;
    }
}
return result;  // Correct

Mistake 3: Wrong edge case handling

// ❌ WRONG - Fails for x = 0 or x = 1
int left = 1;  // Should be 0
int right = x;

// ✓ CORRECT - Handle 0 and 1
if (x < 2) return x;
int left = 0;

Mistake 4: Using float/double

// ❌ WRONG - Problem says not to use pow or exponents
return (int) Math.sqrt(x);  // Not allowed!
return (int) Math.pow(x, 0.5);  // Not allowed!

// ✓ CORRECT - Binary search
// (Our solution)

Mistake 5: Setting right = x for large x

// ⚠️ INEFFICIENT but works
int right = x;  // For x = 2^31, unnecessary large range

// ✓ BETTER - Optimize right bound
int right = Math.min(x, 46341);  // √(2^31) ≈ 46340

// But for simplicity, right = x is fine
// Binary search is fast anyway!

🎯 Pattern Recognition

Problem Type: Binary Search - Mathematical/On Answer Space
Core Pattern: Find Largest Value with Constraint

When to Apply:
✓ Mathematical computation without library
✓ Looking for LARGEST/MAXIMUM satisfying condition
✓ Monotonic property: if k works, all < k work
✓ Can check if value is valid
✓ Need O(log n) time

Recognition Keywords:
- "Square root"
- "Rounded down"
- "Must not use built-in"
- Find maximum/largest
- Mathematical constraint

Similar Problems:
- Valid Perfect Square (LC 367)
- Pow(x, n) (LC 50)
- Divide Two Integers (LC 29)
- Guess Number Higher or Lower (LC 374)
- First Bad Version (LC 278)

Key Difference from Other BS:
┌────────────────────────────────────────────┐
│ Find First/Minimum:                        │
│   - Search for smallest valid              │
│   - right = mid when valid                 │
│                                            │
│ Find Last/Maximum (This Problem):         │
│   - Search for largest valid               │
│   - result = mid when valid                │
│   - left = mid + 1 to find larger          │
└────────────────────────────────────────────┘

Track best answer and keep searching!

🧠 Interview Strategy

Step 1: "Need to find largest k where k² ≤ x"
Step 2: "This is binary search on answer space [0, x]"
Step 3: "Pattern: [valid valid ... | invalid invalid ...]"
Step 4: "Track best valid, keep searching for larger"
Step 5: "Use long for overflow prevention"

Key Points to Mention:
- Binary search on RANGE, not array
- Looking for LARGEST valid number
- Track result as best valid found
- Continue searching for larger valid
- Cast to long prevents overflow
- Handle edge cases x < 2
- Time: O(log x), Space: O(1)
- Can't use Math.sqrt() or pow()

Why This Approach?
"I need to find the largest integer whose square is at most x.
This is perfect for binary search on the answer space [0, x].
The property is monotonic - if k is too large, all larger values
are also too large. I'll track the best valid answer found so far
and keep searching for a larger one. The critical detail is using
long when calculating mid squared to avoid integer overflow for
large values of x."

Overflow Handling:
"When mid is large, mid × mid can overflow integer range. For
example, 46341 squared is over 2 billion. So I cast to long
before multiplication to handle this safely."

📝 Quick Revision Notes

🎯 Core Concept:

Find Square Root (floor): Find largest k where k² ≤ x using binary search on range [0, x]. Track best valid answer. When valid: save and search right. When invalid: search left. Critical: Use long for square calculation!

⚡ Quick Implementation:

class Test {
  public int mySqrt(int x) {
    int left = 0; // since in question, 0 is also in range of inputs
    int right = x;
    int res = 0;

    while (left <= right) {
      int mid = left + (right - left) / 2;
      long product = (long) mid * mid;

      if(product == x) {
        return mid;
      } else if(product < x) {
        // mid is valid, but there might be larger valid number
        // hence could be a potential answer
        res = mid;
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }

    return res;
  }

  public static void main(String[] args) {
    Test t = new Test();
    for(int i = 0; i < 17; i++) {
      System.out.println("for i = "+i+": "+t.mySqrt(i));
    }    
  }
}

🔑 Key Insights:

Pattern: Binary Search on Answer Space / Find Maximum
Goal: Largest k where k² ≤ x
Monotonic: If k² > x, then (k+1)² also > x
Track Result: Save best valid answer
Search Right: When valid, look for larger
Search Left: When invalid, look for smaller
Overflow: Use (long) mid * mid ← CRITICAL!
Edge Cases: x < 2 handled separately
Loop: left <= right (standard BS)
Time: O(log x), Space: O(1)

🎪 Memory Aid:

"Find the LAST valid, track the BEST! Cast to LONG to avoid the test!"
Think: "Largest k² ≤ x = Track best valid!"

💡 The Key Insight:

When mid² ≤ x:
  result = mid (save it!)
  left = mid + 1 (find larger!)

When mid² > x:
  right = mid - 1 (too big!)

When mid² == x:
  return mid (exact!)

⚠️ Critical Details:

1. Edge case: if (x < 2) return x
2. Overflow: long square = (long) mid * mid
3. Track: result = mid when valid
4. Search: left = mid + 1 when valid
5. Loop: while (left <= right)
6. Return: result (best valid found)

🔥 The Overflow Issue:

For large x near 2^31:
  mid can be ~46340
  mid × mid as int: OVERFLOW!
  mid × mid as long: Correct ✓

Example:
  mid = 46341
  As int: mid * mid = negative (overflow!)
  As long: (long) mid * mid = 2,147,488,281 ✓

Always: (long) mid * mid
Never: mid * mid

🎯 The Pattern - Find Last Valid:

Search space: [0, x]
Property: k² ≤ x

[0, 1, 2, ..., k, k+1, ..., x]
[✓  ✓  ✓  ...  ✓   ✗  ...  ✗]
                ↑
           Find this!

When ✓: save it, search right (maybe larger ✓)
When ✗: search left (need smaller)

After loop: result = rightmost ✓

💡 Why Track Result:

Without tracking:
  Find valid mid = 2
  Search right for larger
  Find invalid mid = 3
  Search left
  Loop ends
  Lost the answer 2!

With tracking:
  Find valid mid = 2
  result = 2 (saved!)
  Search right
  Find invalid mid = 3
  Search left
  Loop ends
  Return result = 2 ✓

🧪 Edge Cases

Case 1: x = 0

Input: 0
Output: 0
√0 = 0

Case 2: x = 1

Input: 1
Output: 1
√1 = 1

Case 3: Perfect square

Input: x = 16
Output: 4
√16 = 4 exactly

Case 4: Not perfect square

Input: x = 8
Output: 2
√8 ≈ 2.828, floor = 2

Case 5: Large number

Input: x = 2147395599
Output: 46339
Without long cast: OVERFLOW!
With long cast: Correct ✓

Case 6: x = 2

Input: 2
Output: 1
√2 ≈ 1.414, floor = 1

All handled correctly! ✓

Valid Perfect Square (LC 367) - Similar but checks exact match
Pow(x, n) (LC 50) - Binary search for exponentiation
Divide Two Integers (LC 29) - Binary search for division
First Bad Version (LC 278) - Binary search on range

Happy practicing! 🎯

Note: This is a classic "binary search on answer space" problem! The overflow prevention with long cast is the critical detail that many candidates miss!

56. Sqrt(x)

Problem Statement

🎨 Visual Understanding

The Problem Visualized

🚨 CRITICAL INSIGHT - Why Binary Search Works

Why This is Binary Search on Answer Space

The Binary Search Invariant

🎯 Approach 1: Linear Search (Brute Force)

The Most Natural Thinking 💭

Implementation

🎯 Approach 2: Binary Search (Optimal) ⭐

Better Approach 💡

Implementation

🔍 Dry Run

🎯 Why This Works - Deep Dive

The "Find Last Valid" Pattern

⚠️ Common Mistakes to Avoid

🎯 Pattern Recognition

🧠 Interview Strategy

📝 Quick Revision Notes

🧪 Edge Cases

Related Patterns