## Similar Problems

Similar Problems not available

# Sqrtx - Leetcode Solution

LeetCode: Sqrtx Leetcode Solution

Difficulty: Easy

Topics: math binary-search

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:

- Define a variable ‘left’ as 0, and another variable ‘right’ as x.
- 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.
- If x is 0, return 0 as the square root of 0.
- If x is 1, return 1 as the square root of 1.
- 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.

## Sqrtx Solution Code

`1`