algoadvance

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

Before we start, let’s clarify a few things:

  1. What is the range of x?
    • The problem doesn’t state explicitly, but typically, 0 <= x <= 2^31 - 1 (which is the range of a non-negative 32-bit integer).
  2. What should be the return type?
    • The return type should be an integer.
  3. Is there any specific time complexity constraint?
    • We should aim for an efficient solution, ideally with a time complexity better than O(x).

Strategy

To solve this problem, we can use binary search since it provides an efficient way to find the square root in a log-scale time complexity. Binary search helps us reduce the potential range of square roots at each step by half.

Steps:

  1. Initialize left to 0 and right to x.
  2. While left is less than or equal to right:
    • Compute mid as (left + right) // 2.
    • Compute mid_squared as mid * mid.
    • If mid_squared equals x, return mid.
    • If mid_squared is less than x, set left to mid + 1 (since we need a larger number).
    • If mid_squared is greater than x, set right to mid - 1 (since we need a smaller number).
  3. If no exact square root is found (i.e., mid_squared never equals x), right will be the floor of the square root when the loop terminates.

Time Complexity

The time complexity of this approach is O(log x), as each iteration of the binary search reduces the search space by half.

Code

Here’s a Python implementation of the above strategy:

def mySqrt(x: int) -> int:
    if x < 2:
        return x

    left, right = 0, x

    while left <= right:
        mid = (left + right) // 2
        mid_squared = mid * mid

        if mid_squared == x:
            return mid
        elif mid_squared < x:
            left = mid + 1
        else:
            right = mid - 1

    return right

Explanation

  1. Base Case: If x is less than 2, return x. This covers the edge cases for 0 and 1.
  2. Binary Search Loop:
    • Calculate mid and mid_squared.
    • Adjust left and right based on the comparison between mid_squared and x.
    • If mid_squared matches x, return mid.
    • Continue until left exceeds right.
  3. Return the Floor Value: When the loop terminates without finding an exact match, right will hold the largest integer whose square is less than or equal to x.

This solution efficiently computes the integer square root by leveraging binary search and runs in logarithmic time relative to the input size.

Try our interview co-pilot at AlgoAdvance.com