LeetCode Solution: 69. Sqrt(x)

#leetcode #dsa #programming #tutorial

Unlocking the Power of Binary Search: Solving Sqrt(x) ⚡

Hey awesome coders! 👋 Vansh here, ready to demystify another LeetCode classic. 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 like pow(x, 0.5) or x ** 0.5. This challenge pushes us to think deeper and build our own solution from scratch.

Don't worry, even if you're just starting your coding journey, we'll break down this problem step by step, making it super accessible and fun! By the end, you'll have a powerful new tool in your algorithmic belt: Binary Search.

🧐 Problem Explanation: What are we actually doing?

Imagine you're given a number, let's say x. Your mission is to find its square root. But there's a catch: you need to round the result down to the nearest whole number.

For example:

If x = 4, the square root is exactly 2. So, we return 2.
If x = 8, the square root is approximately 2.82842.... Since we need to round down, we return 2.

The problem also tells us x will always be a non-negative integer. And remember, no built-in square root functions allowed!

🤔 Intuition: The "Aha!" Moment

How would you find the square root of a number x if you could only use multiplication and comparison?

Let's take x = 25.

Is 1 * 1 equal to 25? No, too small.
Is 2 * 2 equal to 25? No.
...
Is 5 * 5 equal to 25? Yes! So 5 is the answer.

What about x = 8?

1 * 1 = 1 (too small)
2 * 2 = 4 (too small)
3 * 3 = 9 (too large!)

Since 3 * 3 is too large, and 2 * 2 is the largest square less than or equal to 8, our answer (rounded down) must be 2.

Notice a pattern? As we try larger numbers, their squares also get larger. This monotonic property (always increasing) is a huge hint! It screams Binary Search!

Binary search is super efficient for finding a target value within a sorted range. Here, we're looking for a number ans such that ans * ans <= x and (ans + 1) * (ans + 1) > x.

🚶‍♀️ Approach: Step-by-Step with Binary Search

Let's outline our binary search strategy:

Define Search Space: What's the possible range for our square root?
- The smallest possible square root is 0 (for x=0).
- The largest possible square root for x will be x itself (since 1*1=1, x*x will be much larger than x unless x=1 or x=0). So, our search space [start, end] can be [0, x]. For x=0, the answer is 0. For x=1, the answer is 1. We can safely start our search from 1 if x > 0.
Initialize Variables:
- s (start): 1 (or 0 for x=0 edge case)
- e (end): x
- ans: A variable to store our potential answer, initialized to 0. This will eventually hold the largest mid whose square is less than or equal to x.
The Loop: We'll use a while loop that continues as long as s <= e.
Calculate mid: In each iteration, find the middle of our current search space:
mid = s + (e - s) / 2;
This way of calculating mid (s + (e - s) / 2) is safer than (s + e) / 2 because it prevents potential integer overflow if s and e are very large.
Calculate square: Compute the square of mid:
long long int square = mid * mid;
Crucial Point: mid * mid can become very large and exceed the maximum value of an int if x is large (e.g., x = 2^31 - 1). To prevent overflow, we must use long long int for square.
Compare and Adjust:
- If square == x: We found the exact square root! Return mid.
- If square < x: This mid is a potential candidate for our answer (since we need to round down, and its square is not too big). Store mid in ans. Now, we need to check if we can find an even larger number whose square is still less than or equal to x. So, we shift our search to the right half: s = mid + 1;
- If square > x: This mid is too large, its square exceeds x. We need to look for smaller numbers. So, we shift our search to the left half: e = mid - 1;
Return ans: Once the loop finishes (s > e), ans will hold the largest integer whose square was less than or equal to x. This is exactly our desired rounded-down square root!

💻 Code

Let's put it all together in C++:

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

        // Initialize our search range
        // The square root of x will be between 1 and x (inclusive for x=1)
        long long s = 1;
        long long e = x;

        // 'ans' will store the potential answer (the largest integer whose square is <= x)
        long long ans = 0;

        // Perform binary search
        while (s <= e) {
            // Calculate mid to prevent potential integer overflow for large s and e
            long long mid = s + (e - s) / 2;

            // Calculate the square of mid.
            // Use long long to prevent overflow if mid * mid exceeds int max value.
            long long square = mid * mid;

            if (square == x) {
                // Found the exact square root, return it immediately
                return mid;
            } else if (square < x) {
                // If mid*mid is less than x, mid could be our answer.
                // Store it and try to find a larger potential answer in the right half.
                ans = mid;
                s = mid + 1;
            } else { // square > x
                // If mid*mid is greater than 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 the square root rounded down.
        return ans;
    }
};

⏱️ Time & Space Complexity Analysis

Time Complexity: O(log x)
Binary search works by repeatedly dividing the search space in half. For a search space of size x, it takes log x operations to find the target. This is incredibly efficient!
Space Complexity: O(1)
We are only using a few constant variables (s, e, mid, ans, square) regardless of the input x. Therefore, the space complexity is constant.

✨ Key Takeaways

Binary Search Power: Whenever you see a problem asking to find a value within a sorted (or monotonically increasing/decreasing) range, think Binary Search!
Preventing Overflow: Be mindful of potential integer overflows, especially when multiplying large numbers. Using long long int is a common fix.
Rounding Down: For "round down" problems, binary search often involves storing a potential_answer and then trying to find a better one in the appropriate half.

This problem is a fantastic entry point into binary search and a great way to build your foundational algorithmic skills. Keep practicing, and you'll be a LeetCode master in no time! Happy coding! 🚀

^{Authored by Vansh2710 | Published on 2026-05-02 18:25:11}