algoadvance

Leetcode 69. Sqrt(x)

Problem Statement

The problem is to implement the function int mySqrt(int x) that computes and returns the square root of x rounded down to the nearest integer. In other words, it returns the greatest integer q such that q^2 is less than or equal to x.

For example:

The input x is a non-negative integer, and we need to ensure the solution handles edge cases such as x = 0.

Clarifying Questions

  1. Can x be a negative number?
    • No, according to the problem statement, x is a non-negative integer.
  2. What is the maximum value of x?
    • The value of x can be as large as the maximum value for an integer (2^31 - 1).
  3. Should we consider any floating-point precision errors?
    • No, the result should be an integer.

Strategy

A simple way to solve this problem is by using binary search:

  1. Initialize left to 0 and right to x.
  2. Use binary search to find the largest integer mid such that mid * mid <= x.
  3. Adjust left and right based on the comparison of mid * mid with x.

The binary search approach will ensure we have a time complexity of O(log x), which is efficient for handling up to the maximum possible value of x.

Code

Here is the C++ implementation of the described strategy:

class Solution {
public:
    int mySqrt(int x) {
        if (x == 0) return 0; // Handle the edge case where x is 0

        int left = 1, right = x, ans = 0;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (mid <= x / mid) { // Avoiding overflow with mid*mid <= x
                ans = mid;
                left = mid + 1; // Try for a higher number
            } else {
                right = mid - 1; // Try for a lower number
            }
        }
        return ans;
    }
};

Time Complexity

The time complexity of this solution is O(log x) due to the binary search mechanism. This ensures that for very large values of x (up to 2^31 - 1), the computation remains efficient. The space complexity is O(1) as we are using a constant amount of space.

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