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