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 while (left <= right) {
6 int mid = left + (right - left) / 2;
7 if (mid <= x / mid) {
8 left = mid + 1;
9 } else {
10 right = mid - 1;
11 }
12 }
13 return right;
14 }
15
16 public static void Main(string[] args) {
17 Solution sol = new Solution();
18 int x = 8;
19 Console.WriteLine(sol.MySqrt(x)); // Output: 2
20 }
21}This C# solution finds the integer square root by using binary search within the method MySqrt inside a class Solution. It repeatedly adjusts the search range based on the comparisons.
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.