algoadvance

Leetcode 69. Sqrt(x)

Problem Statement

Given a non-negative integer x, compute and return the square root of x.

Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned.

Example 1:

Input: x = 4
Output: 2

Example 2:

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.

Clarifying Questions

1. Q: What is the range of input values?
   • A: The input x is a non-negative integer. There are no specific constraints, but typically for such problems, the value of x can be large, up to (2^{31} - 1) (the maximum value for a 32-bit signed integer).
2. Q: Should we consider mathematical functions like Math.sqrt()?
   • A: For learning and interview purposes, it is better to implement the algorithm without using Math.sqrt(), as it demonstrates problem-solving skills and understanding of algorithms.
3. Q: How do we handle edge cases such as x = 0 or x = 1?
   • A: These should be handled specifically. The square root of 0 is 0, and the square root of 1 is 1.

Strategy

We can solve this problem using the Binary Search algorithm:

1. Initialize: Start with two pointers, left = 0 and right = x.
2. Binary Search: While left <= right, calculate the mid-point, mid = left + (right - left) / 2.
3. Check:
   • If mid * mid equals x, return mid.
   • If mid * mid is less than x, move left to mid + 1.
   • If mid * mid is greater than x, move right to mid - 1.
4. Return: When the loop ends, right will be the integer part of the square root.

Code

public class Solution {
    public int mySqrt(int x) {
        if (x < 2) {
            return x;
        }
        
        int left = 0;
        int right = x;
        int result = 0;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (mid <= x / mid) {
                result = mid;  // mid is a potential answer
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return result;
    }
}

Time Complexity

• Time Complexity: O(log x), because we are using binary search which divides the range in half for each iteration.
• Space Complexity: O(1), as we are using a constant amount of extra space.

This solution efficiently finds the integer part of the square root using binary search without relying on built-in functions, making it suitable for large input values.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?