Root of Number (Java solution)
a Question on Pramp platform
In this question, we will need to re-implement a function to calculate the n’th root of number. The input of the function is a nonnegative number x and a positive integer n. In the end, the function should return the positive n’th root of x within an error of 0.001. Besides, we should not use Math.power() or other standard library functions to solve this question.
import java.io.*;
import java.util.*;class Solution {
static double root(double x, int n) {
}
}
The two examples that question provides:
input: x = 7, n = 3 output: 1.913
input: x = 9, n = 2 output: 3The most efficient way to solve this question is to solve it with binary search because it can make the time complexity reach O(log(n)).
The first step is that we set the left pointer to 0 and the right pointer to the x. The initial guess of the root value is the number in between 0 and x, and then we set it to the average value of the two pointers. Since we can only tolerate error less than 0.001, we have to make sure that after iterating the while loop, the mid value(the answer that the function returns) is within our error tolerance 0.001.
static double root(double x, int n) {
// your code goes here
if(x == 0) return 0;
double left = 0, right = x;
double mid = (right+left)/2; while(mid - left >= 0.001){
if(helper(mid, n) > x ){
right = mid;
}else if(helper(mid, n) < x){
left = mid;
}else{
return mid;
}
mid = left + (right - left) / 2;
}
return mid;
}
In the helper function, we are going to calculate the val to the power n because we can’t use any standard library function in this question. We have to implement one on our own. Therefore, we start our return ans with1 and keep multiplying it with val for n times. In the end, the helper function can correctly return what we want.
static double helper(double val, int n){
double ans = 1;
for(int i = 1; i <= n; i++){
ans *= val;
}
return ans;
}My pramp invite link:
