Sqrtx - Leetcode Solution

The problem statement for the Sqrtx problem on LeetCode is as follows:

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

Since the output has to be an integer, we need to use integer division instead of floating-point division while calculating the square root of x.

Approach:

One way to approach this problem is to perform a binary search on the possible integer values (0 to x) to determine the integer value which when squared is closest to x.

Algorithm:

1. Define a variable ‘left’ as 0, and another variable ‘right’ as x.
2. While left is less than or equal to right, perform the following steps: a. Define a variable ‘mid’ as the integer division of the sum of left and right by 2. b. Calculate the square of mid as ‘square_mid’. c. Compare square_mid with x and perform the following: i. If square_mid is less than x, make left equal to mid + 1. ii. If square_mid is greater than x, make right equal to mid - 1. iii. If square_mid is equal to x, return mid as the square root of x.
3. If x is 0, return 0 as the square root of 0.
4. If x is 1, return 1 as the square root of 1.
5. If the square root of x is not an integer, return the integer part of the square root of x.

Code:

Here is the Python code for the above algorithm:

class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 0:
            return 0
        if x == 1:
            return 1
        left, right = 0, x
        while left <= right:
            mid = (left+right)//2
            if mid*mid == x:
                return mid
            elif mid*mid < x:
                left = mid + 1
            else:
                right = mid - 1
        return right

Time Complexity: O(log n) where n is the given number, as we are performing a binary search.

Space Complexity: O(1) as we are not using any extra space.

Note: The code above has been minimally edited from the original to ensure that it is in line with our guidelines.

1