LeetCode 69: Sqrt(x) Solution

Problem Explanation

Explanation

To find the square root of a non-negative integer x without using any built-in exponent function or operator, we can use binary search. We start with a range [0, x] and iteratively narrow down the range until we find the square root. At each iteration, we calculate the mid-point of the current range and check if the square of the mid-point is greater, equal to, or less than x. Based on this comparison, we update the range to search in. We continue this process until we find the integer square root.

Algorithm:
1. Initialize left to 0 and right to x.
2. While left <= right, calculate the mid-point mid as (left + right) / 2.
3. If mid * mid == x, return mid.
4. If mid * mid < x, update left to mid + 1.
5. If mid * mid > x, update right to mid - 1.
6. Return right as the integer square root of x.
Time Complexity: O(log(x)) - Binary search reduces the search range by half in each iteration.
Space Complexity: O(1) - Constant extra space is used.

Solution Code

class Solution {
    public int mySqrt(int x) {
        if (x == 0) return 0;
        long left = 1, right = x;
        while (left < right) {
            long mid = left + (right - left) / 2;
            if (mid * mid == x) return (int)mid;
            else if (mid * mid < x) left = mid + 1;
            else right = mid;
        }
        return (int)right - 1;
    }
}

Frequently Asked Questions

How to solve LeetCode 69 (Sqrt(x))?

This page provides optimized solutions for LeetCode problem 69 (Sqrt(x)) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 69 (Sqrt(x))?

The time complexity for LeetCode 69 (Sqrt(x)) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 69 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 69 in Java, C++, or Python.