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)
1public class Solution {
2 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;
}
public static void Main(string[] args) {
Solution sol = new Solution();
int x = 8;
Console.WriteLine(sol.MySqrt(x)); // Output: 2
}
}The C# solution uses Newton's iterative method to compute the integer square root through continuous refinement of g.