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)
1function mySqrt(x) {
2 if (x < 2) return x;
3 let left = 1, right = Math.floor(x / 2);
4 while (left <= right) {
5 let mid = Math.floor((left + right) / 2);
6 if (mid <= Math.floor(x / mid)) {
7 left = mid + 1;
8 } else {
9 right = mid - 1;
10 }
11 }
12 return right;
13}
14
15let x = 8;
16console.log(mySqrt(x)); // Output: 2
17The JavaScript solution utilizes binary search by initializing the range and continuously updating the potential midpoint until it narrows down on the correct integer square root value.
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)
1public
This Java implementation uses the iterative Newton's method to find the approximate integer square root by continuously updating the guess g.