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 <stdio.h>
2
3int mySqrt(int x) {
4 if (x < 2) return x;
5 int left = 1, right = x / 2, mid;
6 while (left <= right) {
7 mid = left + (right - left) / 2;
8 if (mid <= x / mid) {
9 left = mid + 1;
10 } else {
11 right = mid - 1;
12 }
13 }
14 return right;
15}
16
17int main() {
18 int x = 8;
19 printf("%d", mySqrt(x)); // Output: 2
20 return 0;
21}
22This implementation uses binary search. The mySqrt function initializes two pointers, left and right, to define the search space. The mid-point is calculated, and the square of the mid-point is compared with x. The search space is adjusted accordingly until it converges.
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)
1#include <iostream>
2using namespace std;
class Solution {
public:
int mySqrt(int x) {
if (x < 2) return x;
double g = x;
while (g * g > x) {
g = (g + x / g) / 2;
}
return (int)g;
}
};
int main() {
Solution sol;
int x = 8;
cout << sol.mySqrt(x) << endl; // Output: 2
return 0;
}The C++ solution uses the Newton-Raphson iterative formula to continually improve the estimate of the square root until convergence.