[Leetcode][69. Sqrt(x)] 4 Approaches for Finding the Square Root of A Number: BF, Exponent, Binary Search and Newton Iteration Method

By Long Luo

This article is the solution of Leetcode Problem 69. Sqrt(x).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
69. Sqrt(x)

Easy

Given a non-negative integer x, compute and return the square root of x. Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned.

Note: You are not allowed to use any built-in exponent function or operator, such as pow(x, 0.5) or x ** 0.5.

Example 1:
Input: x = 4
Output: 2

Example 2:
Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.

Constraints:
0 <= x <= 2^31 - 1

Given an integer NN and a tolerance level LL, the task is to find the square root of that number.

Brute Force

The Brute Force way is very easy, just enumerate a value from 00 to xx, check the product i2i^2 and target, return the answer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int mySqrt(int x) {
if (x == 0 || x == 1) {
return x;
}

for (int i = 0; i < x; i++) {
long sum = i * i;
long bigger = (long) (i + 1) * (i + 1);
if (sum == x) {
return i;
} else if (sum < x && bigger > x) {
return i;
}
}

return 0;
}

Analysis

  • Time Complexity: O(n)O(n)
  • Space Complexity: O(1)O(1).

Exponent

Noted that:

x=x1/2=(elnx)1/2=e12lnx\sqrt{x} = x^{1/2} = (e ^ {\ln x})^{1/2} = e^{\frac{1}{2} \ln x}

So we can use the exponent exp\exp and logarithm ln\ln to calculate the square root of the number x\sqrt{x}.

It’s really a fast and simple way!

Note: Since the computer can’t store the exact value of the float number, and the parameters and return values of the exponential function and logarithmic function are float numbers, so the result may be wrong.

For example, when x=2147395600x = 2147395600, the result of e12lnxe^{\frac{1}{2} \ln x} is 101110^{-11} from the correct value of 4634046340, so when taking the integer part of the result, you will get the wrong result of 4633946339.

So after getting the integer part ans\textit{ans} of the result, we should find out which of ans\textit{ans} and ans+1\textit{ans} + 1 is the real answer.

1
2
3
4
5
6
7
8
// Exp O(1) O(1)
public static int mySqrt_exp(int x) {
if (x == 0) {
return 0;
}
int ans = (int) Math.exp(0.5 * Math.log(x));
return (long) (ans + 1) * (ans + 1) <= x ? ans + 1 : ans;
}

Analysis

  • Time Complexity: O(1)O(1)
  • Space Complexity: O(1)O(1).

Binary Search

We can use Binary Search to solve this problem.

Let the square root of xx is kk, k2xk^2 \leq x. The lower bound is 00, and the upper bound is xx. In each step, we need to compare the middle element mid2xmid^2 \leq x or mid2>xmid^2 > x, adjust the range of the upper and lower bounds.

Since all our operations are integer operations, there is no error, so after getting the final answer ans\textit{ans}, there is no need to try ans+1\textit{ans} + 1 again.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static int mySqrt_bs_opt(int x) {
if (x <= 1) {
return x;
}

int left = 1;
int right = x / 2;
while (left < right) {
int mid = left + (right - left + 1) / 2;
if (mid > x / mid) {
right = mid - 1;
} else {
left = mid;
}
}

return left;
}

Analysis

  • Time Complexity: O(logx)O(\log x)
  • Space Complexity: O(1)O(1).

Newton’s Method

The Newton’s Method is:

Let NN be any number then the square root of NN can be given by the formula:

root=0.5×(X+(N/X))root = 0.5 \times (X + (N / X))

where XX is any guess which can be assumed to be NN or 11.

  1. In the above formula, XX is any assumed square root of NN and root is the correct square root of NN.
  2. Tolerance limit is the maximum difference between XX and root allowed.

But how to understand this method?

If we want to find the square root of the integer NN. Obviously, the square root of NN is the function y=f(x)=x2Ny = f(x) = x^2 - N of zero.

Newton Iteration Method

We take any xnx_n as an initial value, at each iteration of the step. We find the point (xn,f(xn))(x_n, f(x_n)) on the image of the function, make a slope through this point, the derivative of this point f(xn)f'(x_n), the intersection with the horizontal axis is denoted as xn+1x_{n+1} compared to xnx_n. It’s closer to zero.

The equation of the straight line is:

2×xn=(xn2N)/(xnx)2 \times x_n = (x_n^2 - N) / (x_n - x)

The intersection with the horizontal axis is the equation:

2×xn×x(xn2+N)=02 \times x_n \times x - (x_n^2 + N) = 0

which is the new iteration result xn+1x_{n+1}:

xn+1=0.5×(xn+N/xn)x_{n+1} = 0.5 \times (x_n + N / x_n)

After iterations, the value of the true zero point sqrt(N)sqrt(N) is close enough to be an answer.

There comes two questions:

  1. Which initial value do we assign?
  2. When does the iteration end?

Initial value

As mentioned rule 1, we assign XX to the NN itself because we want to find the positive sqrt(N)sqrt(N) and NN is surely larger than sqrt(N)sqrt(N).

Ending iteration

After each iteration, the answer is closer to the zero point. So when the intersection obtained from two adjacent iterations is very close, we can conclude that the result at this time is enough for us to get the answer.

As mentioned rule 2, if the calculated root comes inside the tolerance allowed then break out of the loop.

In general, it can be judged whether the difference between the results of two adjacent iterations is less than a very small non-negative number.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int mySqrt_newton(int x) {
if (x == 0) {
return 0;
}

double N = x;
double x0 = x;
while (true) {
double xi = 0.5 * (x0 + N / x0);
if (Math.abs(x0 - xi) < 1e-7) {
break;
}
x0 = xi;
}

return (int) x0;
}

Analysis

  • Time Complexity: O(logx)O(\log x)
  • Space Complexity: O(1)O(1).

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗