[Leetcode][69. Sqrt(x)] 4 Approaches for Finding the Square Root of A Number: Brute Force, Exponent, Binary Search and the Newton Iteration Method
By Long Luo
This article is the solution 4 Approaches: Brute Force, Exponent, Binary Search and the Newton’s Iteration Method of Problem 69. Sqrt(x).
Here shows 4 approaches for finding the square root of a number: Brute Force, Exponent, Binary Search and the Newton’s Iteration Method.
Given an integer and a tolerance level , 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 to , check the product and target, return the answer.
1 | public static int mySqrt(int x) { |
Analysis
- Time Complexity:
- Space Complexity: .
Exponent
Noted that:
So we can use the exponent and logarithm to calculate the square root of the number .
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 , the result of is from the correct value of , so when taking the integer part of the result, you will get the wrong result of .
So after getting the integer part of the result, we should find out which of and is the real answer.
1 | // Exp O(1) O(1) |
Analysis
- Time Complexity:
- Space Complexity: .
Binary Search
We can use Binary Search to solve this problem.
Let the square root of is , . The lower bound is , and the upper bound is . In each step, we need to compare the middle element or , 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 , there is no need to try again.
1 | public static int mySqrt_bs_opt(int x) { |
Analysis
- Time Complexity:
- Space Complexity: .
Newton’s Method
The Newton’s Method is:
Let be any number then the square root of can be given by the formula:
where is any guess which can be assumed to be or .
- In the above formula, is any assumed square root of and root is the correct square root of .
- Tolerance limit is the maximum difference between and root allowed.
But how to understand this method?
If we want to find the square root of the integer . Obviously, the square root of is the function of zero.
We take any as an initial value, at each iteration of the step. We find the point on the image of the function, make a slope through this point, the derivative of this point , the intersection with the horizontal axis is denoted as compared to . It’s closer to zero.
The equation of the straight line is:
The intersection with the horizontal axis is the equation:
which is the new iteration result :
After iterations, the value of the true zero point is close enough to be an answer.
There comes two questions:
- Which initial value do we assign?
- When does the iteration end?
Initial value
As mentioned rule 1, we assign to the itself because we want to find the positive and is surely larger than .
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 | public static int mySqrt_newton(int x) { |
Analysis
- Time Complexity:
- Space Complexity: .
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. 😉😃💗