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:

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.

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;
    }
}