LeetCode Solution: 69. Sqrt(x)

✨ Unlocking Sqrt(x): Your First Dive into Binary Search! 🚀

Hey amazing developers! 👋 Vansh2710 here, ready to embark on another exciting LeetCode adventure with you. Today, we're tackling problem #69: Sqrt(x). Sounds simple, right? Just find the square root! But here's the twist: we can't use any fancy built-in functions. We're going old-school and building our own square root finder from scratch. Get ready to discover the magic of Binary Search!

---

🧐 Problem Explanation: What are we actually doing?

The problem asks us to find the square root of a given non-negative integer x. The catch? We need to round down the result to the nearest whole number. So, if sqrt(x) is 2.828..., we return 2. And a critical constraint: NO built-in functions like pow(x, 0.5) or x ** 0.5 allowed! This means we have to come up with our own algorithm.

Let's look at the examples:

• Example 1: x = 4

  • The square root of 4 is exactly 2.
  • Output: 2

• Example 2: x = 8

  • The actual square root of 8 is approximately 2.82842...
  • When we round this down to the nearest integer, we get 2.
  • Output: 2

The constraints tell us x can be pretty large (0 <= x <= 2^31 - 1), so our solution needs to be efficient!

---

🤔 Intuition: How would you guess the square root?

Imagine you're a human calculator, and I ask you to find the square root of, say, 49. How would you do it without a calculator?

You'd probably start guessing:

• "Is it 1? 1 * 1 = 1 (Too small!)"
• "Is it 10? 10 * 10 = 100 (Too big!)"
• "Okay, somewhere between 1 and 10. Let's try 5. 5 * 5 = 25 (Still too small!)"
• "Let's try 8. 8 * 8 = 64 (Too big!)"
• "Okay, between 5 and 8. How about 7? 7 * 7 = 49 (Bingo! Just right!)"

Notice a pattern here? You're constantly narrowing down your search space based on whether your guess squared is too small or too big. This exact thought process is the cornerstone of an incredibly powerful algorithm: Binary Search!

---

🚀 Approach: Binary Search to the Rescue!

Binary Search is perfect for problems where you need to find a specific value within a sorted range or determine a "point" where a condition changes (like y*y goes from less than x to greater than x).

Here's how we'll apply it:

1. Define our Search Space: What's the smallest possible square root for x? 0 (for x=0). What's the largest? It can't be more than x itself (e.g., sqrt(1) is 1). So, our search range will be from 0 (or 1 if we handle x=0 separately) to x. Let's call these s (start) and e (end).

2. Iterate and Conquer: We'll keep guessing the midpoint of our s and e range.

*   Initialize `s = 0` (or `1`), `e = x`.
*   Also, initialize an `ans` variable to store our best possible rounded-down answer, starting at `0` (or `1`).

1. The Loop: While s is less than or equal to e (meaning our search space is still valid):

*   **Calculate `mid`:** `mid = s + (e - s) / 2;` (This way of calculating `mid` prevents potential integer overflow compared to `(s+e)/2` if `s` and `e` are very large).

*   **Calculate `square`:** `long long square = mid * mid;`
    *   **CRITICAL STEP:** We use `long long` here! Why? Because `x` can be up to `2^31 - 1`. If `mid` is, say, `60000`, `mid * mid` is `3,600,000,000`, which is larger than the maximum value for a standard `int` (`~2*10^9`). Using `long long` prevents overflow and ensures our calculations are accurate.

*   **Compare `square` with `x`:**
    *   **Case 1: `square == x`**
        *   We found the exact square root! Return `mid` immediately.
    *   **Case 2: `square < x`**
        *   `mid` is too small, or it *could* be our rounded-down answer, but we might find a larger, more accurate one.
        *   So, we store `mid` in `ans` (because `mid` is the largest integer whose square is `_less than or equal to_ x` *so far*).
        *   Then, we search in the **right half** to find a potentially larger `mid`: `s = mid + 1;`
    *   **Case 3: `square > x`**
        *   `mid` is too big. Its square exceeds `x`.
        *   We need to search in the **left half**: `e = mid - 1;`

1. Return ans: After the loop finishes (when s becomes greater than e), our ans variable will hold the largest integer y such that y * y <= x. This is precisely the square root of x rounded down!

---

💻 Code (C++)

class Solution {
public:
    int mySqrt(int x) {
        // Handle edge case for x = 0
        if (x == 0) {
            return 0;
        }

        // Initialize our binary search range
        // The square root of x will be between 1 and x
        long long s = 1;         // 's' for start
        long long e = x;         // 'e' for end
        long long ans = 1;       // To store the potential answer (rounded down)

        // Perform binary search
        while (s <= e) {
            // Calculate mid-point. Using this formula to prevent potential overflow
            // if s and e were both very large and their sum exceeded MAX_INT
            long long mid = s + (e - s) / 2;

            // Calculate the square of mid. Use long long to prevent overflow
            // since mid * mid could exceed the maximum value of an int.
            long long square = mid * mid;

            if (square == x) {
                // Found the exact square root, return it
                return mid;
            } else if (square < x) {
                // mid is too small, or it could be our rounded-down answer.
                // We keep mid as a potential answer and try to find a larger one
                // by searching in the right half.
                ans = mid;
                s = mid + 1;
            } else { // square > x
                // mid is too large, search in the left half
                e = mid - 1;
            }
        }

        // After the loop, 'ans' holds the largest integer whose square is less than or equal to x.
        // This is our square root rounded down.
        return ans;
    }
};

---

⏱️ Time & Space Complexity Analysis

• Time Complexity: O(log x)

  • Binary search works by repeatedly halving the search space. If our initial search space has N elements (in our case, x possibilities), it takes log N steps to find the target. Here, N is roughly x, so it's O(log x). This is super efficient for large x!

• Space Complexity: O(1)

  • We are only using a few variables (s, e, mid, square, ans) regardless of the input x. We don't use any extra data structures that grow with the input size.

---

🎯 Key Takeaways

1. Binary Search is Versatile: It's not just for finding exact values! It's incredibly powerful for finding "thresholds" or "transition points" in a sorted or monotonically changing range (like y*y increasing as y increases).
2. Beware of Integer Overflow: Always be mindful of the maximum possible values your variables can hold, especially when multiplying large numbers. long long is your friend!
3. Rounded Down Logic: When a problem asks for a rounded-down (floor) value, you often need to keep track of the "best valid answer so far" when your mid is still too small, but potentially correct.

This problem is a fantastic introduction to the elegance and efficiency of binary search. Keep practicing, and you'll master it in no time! Happy coding!

---

Author Account: Vansh2710
Time Published: 2026-05-02 18:31:13