# Solution For Sqrtx

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.

## Step by Step Implementation For Sqrtx

class Solution { public int mySqrt(int x) { if (x == 0) return 0; int left = 1, right = x; while (true) { int mid = left + (right - left)/2; if (mid > x/mid) { right = mid - 1; } else { if (mid + 1 > x/(mid + 1)) return mid; left = mid + 1; } } } }

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

var mySqrt = function(x) { //edge case if (x == 0) return 0; //initiate left and right pointers let left = 1, right = x; //perform binary search while (left <= right) { //calculate middle let middle = Math.floor((left + right) / 2); //if x is a perfect square, return middle if (middle * middle == x) { return middle; } //if x is less than the square of middle, move the right pointer to the left else if (x < middle * middle) { right = middle - 1; } //if x is greater than the square of middle, move the left pointer to the right else { left = middle + 1; } } //after the while loop terminates, left will be greater than right //therefore, left - 1 will be the greatest integer less than the square root of x return left - 1; };

class Solution { public: int mySqrt(int x) { if (x == 0) return 0; int left = 1, right = x; while (true) { int mid = left + (right - left)/2; if (mid > x/mid) { right = mid - 1; } else { if (mid + 1 > x/(mid + 1)) return mid; left = mid + 1; } } } };

public class Solution { public int MySqrt(int x) { // Newton's method // Time complexity: O(logx) // Space complexity: O(1) long r = x; while (r * r > x) { r = (r + x / r) / 2; } return (int) r; } }