LeetCode Problem 69: Sqrt(x) – Solution in Java

Finding the square root of a number is a classic problem in computer science and mathematics. LeetCode’s Problem 69, Sqrt(x), asks us to compute and return the integer part of the square root of a given non-negative integer x. This article will walk through an efficient binary search-based approach to solving this problem in Java.

Problem Description

Given a non-negative integer x, we need to compute and return the square root of x. However, since the return type is an integer, we only need to return the integer part of the square root, discarding any decimal digits.

For example:

Input: x = 8
Output: 2 (since the square root of 8 is approximately 2.828, we return only 2)

Approach to Solving the Problem

Constraints

We are dealing with non-negative integers.
We must avoid using the built-in square root functions (like Math.sqrt()), as the goal is to solve it manually.

A brute-force approach would involve checking every integer i from 1 to x, squaring it, and stopping when i * i exceeds x. However, this can be optimized using binary search.

Why Binary Search?

The square root function is monotonic, meaning it increases continuously. This property makes it an ideal candidate for binary search, which can narrow down the range of possible solutions efficiently.

Using binary search, we can start with a search range of [1, x] and repeatedly narrow it down until we find the largest integer i such that i * i <= x.

Java Solution Using Binary Search

Here’s the full Java solution:

public class SquareRoot {

	public static int getSquareRoot(int num) {
		// Edge case for input 0
		if (num == 0)
			return 0;

		int left = 1, right = num;
		int result = 0; // To store the integer part of the square root

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

			// Check if mid is greater than the square root
			if (mid > num / mid) {
				right = mid - 1;
			} else {
			// mid * mid is less than or equal to num, update the result
				result = mid;
				left = mid + 1;
			}
		}

		return result;
	}

	public static void main(String[] args) {
		int num = 8;
		System.out.println("The square root of " + num + " is: " 
                                                            + getSquareRoot(num));
	}
}

Explanation of the Code

Base Case: We first handle the edge case where the input number is 0, returning 0 directly because the square root of 0 is 0.
Binary Search Initialization:
- We initialize left to 1 and right to num. The variable result will hold the integer part of the square root once found.
Binary Search Loop:
- We repeatedly compute the midpoint mid of the current range [left, right].
- If mid * mid is greater than num, then we know the square root must be smaller, so we move the right boundary to mid - 1.
- If mid * mid is less than or equal to num, we update result to mid and move the left boundary to mid + 1 to see if we can find a larger valid square root.
Returning the Result: Once the loop terminates, result will hold the largest integer x such that x * x <= num.

Time and Space Complexity

Time Complexity: The binary search approach runs in O(log n), where n is the input number. This is because at each step of the binary search, we cut the search range in half.
Space Complexity: The space complexity is O(1), as we are using only a constant amount of extra space (variables left, right, mid, and result).

Example Walkthrough

Let’s walk through an example where x = 8:

Initialize: left = 1, right = 8, result = 0.
First Iteration:
- Compute mid = 1 + (8 - 1) / 2 = 4.
- 4 * 4 = 16, which is greater than 8, so set right = 3.
Second Iteration:
- Compute mid = 1 + (3 - 1) / 2 = 2.
- 2 * 2 = 4, which is less than or equal to 8, so set result = 2 and move left = 3.
Third Iteration:
- Compute mid = 3 + (3 - 3) / 2 = 3.
- 3 * 3 = 9, which is greater than 8, so set right = 2.
End: The loop terminates because left > right, and we return result = 2.

Conclusion

LeetCode Problem 69, Sqrt(x), can be efficiently solved using binary search. The key to this approach is leveraging the monotonic behavior of the square root function, allowing us to narrow down the possible values in logarithmic time. The above Java solution runs in O(log n) time and uses constant space, making it a highly optimized method to compute the integer part of the square root.

This problem is a great exercise in applying binary search to real-world problems, and mastering it will help you build a solid foundation for tackling more complex algorithms.

#LeetCode69 #Sqrt #BinarySearch #Java #InterviewQuestions #AlgorithmSolutions