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)
1public class Solution {
2 public int mySqrt(int x) {
3 if (x < 2) return x;
4 int left = 1, right = x / 2;
5 int ans = 0;
6 while (left <= right) {
7 int mid = left + (right - left) / 2;
8 if (mid <= x / mid) {
9 ans = mid;
10 left = mid + 1;
11 } else {
12 right = mid - 1;
13 }
14 }
15 return ans;
16 }
17
18 public static void main(String[] args) {
19 Solution sol = new Solution();
20 int x = 8;
21 System.out.println(sol.mySqrt(x)); // Output: 2
22 }
23}The Java solution implements a binary search in the method mySqrt inside a class Solution. It maintains a search range and adjusts it based on the comparison of mid * mid and x.
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.