Sponsored
Sponsored
This approach uses binary search to find the integer square root of the given number x. The idea is to use a binary search over the range [0, x] to find the largest number whose square is less than or equal to x. The time complexity of this approach is logarithmic, which makes it very efficient.
Time Complexity: O(log x)
Space Complexity: O(1)
1class Solution:
2 def mySqrt(self, x: int) -> int:
3 if x < 2:
4 return x
5 left, right = 1, x // 2
6 while left <= right:
7 mid = (left + right) // 2
8 if mid <= x // mid:
9 left = mid + 1
10 else:
11 right = mid - 1
12 return right
13
14sol = Solution()
15x = 8
16print(sol.mySqrt(x)) # Output: 2
17This Python solution uses binary search to find the integer square root. It divides the problem space into half iteratively until the square root is found within the defined precision.
Newton's Method (also known as the Newton-Raphson method) can also be applied to find the square root of a number through iteration. The general formula for updating a guess g is g = (g + x/g) / 2. This keeps refining the guess based on how close it is to x/g.
Time Complexity: O(log x)
Space Complexity: O(1)
1class Solution
The Python solution employs Newton's method to iteratively approach the integer square root by refining the guess until convergence.