Calculate Square Root of a Number
Given a non-negative double number, write a function to calculate its square root.
Statement
Given a number of type double, calculate its square root.
Constraints
For this problem, the given number is always a non-negative double number.
Example
Sample input
16.0
Expected output
4.0
Try it yourself
#include <iostream>#include <cmath>#include <vector>using namespace std;// EPSILON is used to denote a small quantity, like an error,// or perhaps a term which will be taken to zero in some limitconst double EPSILON = 0.00001;double SquareRoot(double num) {// TODO: Write - Your - Codereturn num;}
Solution 1
We pass both low
and high
values to each recursive function call, where mid
and square is calculated.
-
If the square of
mid
is equal ton
then it is the base case, and we returnmid
as the square root ofn
. -
If the square of
mid
is smaller thann
then in the next recursive call,low
is changed tomid
andhigh
remains unchanged. -
If the square of
mid
is larger thann
then in the next recursive call,high
is changed tomid
andlow
remains unchanged.
#include <iostream>#include <cmath>#include <vector>using namespace std;// EPSILON is used to denote a small quantity, like an error,// or perhaps a term which will be taken to zero in some limitconst double EPSILON = 0.00001;double SquareRootRec(double num, double low, double high) {double mid = (low + high) / 2;double sqr = mid * mid;// Finds the difference between the calculated square and given numberdouble diff = abs(sqr - num);// we can't do a == b for doubles because// of rounding errors, so we use error threshold// EPSILON. Two doubles a and b are equal if// abs(a-b) <= EPSILONif (diff <= EPSILON) {return mid;}// If the square of mid is smaller than num, then in the next recursive call,// low will be changed to mid and high remains unchanged.if (sqr < num) {return SquareRootRec(num, mid, high);}// Otherwise, that is, if the square of mid is greater than num, then,// in the next recursive call, high will be changed to mid and// low remains unchanged.return SquareRootRec(num, low, mid);}double SquareRoot(double num) {if (num < 0) {return -1;} else {// Calls recursive function with given number, low and highreturn SquareRootRec(num, 0, 1 + num / 2);}}int main() {vector<double> arr = {-16, 17, 2.25};for (int i = 0; i < arr.size(); i++) {double ans = SquareRoot(arr[i]);string ansStr = (ans == -1) ? " Number is negative." : to_string(ans);cout << i + 1 << ". Square root of " << arr[i] << ": " << ansStr << endl;cout << "\n-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------\n" << endl;}}
Time complexity
The time complexity of this solution is logarithmic, .
Space complexity
The space complexity of this solution is logarithmic, .
Solution 2
We can use an algorithm very similar to binary search to find the square root of a number. We know that the square root of a negative number can’t be defined without using complex numbers. As the problem is limited to non-negative numbers only, we will focus on that. It is a good idea to discuss this case with your interviewer.
Let’s assume that the given number is and we have to find its square root, . Below are two known mathematical facts.
- The square root of a number is always smaller than the given number if the number is greater than 1.
...