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, ...
Level up your interview prep. Join Educative to access 70+ hands-on prep courses.