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)
1#include <iostream>
2using namespace std;
3
4class Solution {
5public:
6 int mySqrt(int x) {
7 if (x < 2) return x;
8 int left = 1, right = x / 2, mid, sqrt;
9 while (left <= right) {
10 mid = left + (right - left) / 2;
11 if (mid <= x / mid) {
12 left = mid + 1;
13 sqrt = mid;
14 } else {
15 right = mid - 1;
16 }
17 }
18 return sqrt;
19 }
20};
21
22int main() {
23 Solution sol;
24 int x = 8;
25 cout << sol.mySqrt(x) << endl; // Output: 2
26 return 0;
27}This C++ solution follows the same binary search logic. It uses a class Solution with a method mySqrt that performs the search to find the integer square root.
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)
1function mySqrt
The JavaScript implementation applies the Newton-Raphson method, iteratively refining the guess g until finding the integer square root.