You are given two positive integers 'n' and 'm'. You have to return the 'nth' root of 'm', i.e. 'm(1/n)'. If the 'nth root is not an integer, return -1.
'nth' root of an integer 'm' is a number, which, when raised to the power 'n', gives 'm' as a result.
Input: ‘n’ = 3, ‘m’ = 27
Output: 3
Explanation:
3rd Root of 27 is 3, as (3)^3 equals 27.
The first line of the input consists of two space-separated integers, n and m.
Return an integer that denotes the nth root of m in a separate line. If such an integer doesn't exist return -1.
You don't have to print anything. It has already been taken care of. Just Implement the given function.
3 27
3
3rd Root of 27 is 3, as (3)^3 equals 27.
4 69
-1
4th Root of 69 is not an integer, hence -1.
Try to do this in O(log(n+m)).
1 <= n <= 30
1 <= m <= 10^9
Time Limit: 1 sec.
Is there any monotonic function followed for this problem?
The idea for this approach is to use binary search to find an integer equal to ‘M’ when multiplied by itself ‘N’ times.
The exponential function is an increasing function (i.e., monotonic), and thus, using binary search, we will try out different possible square roots; let’s suppose we are currently on ‘X’, then we will find
To find the value of ‘XN’, we can use a loop, which will iterate ‘N’ times.
The steps are as follows:-
// Function to find the Nth root of M
function NthRoot(int n, int m):
O( n * log(M) ), Where ‘N’ and ‘M’ are input integers.
In the above algorithm, the search space is ‘M’, and hence in ‘log(M)’ iterations, we will find the ‘N’th root, and in each iteration, we find the ‘N’th power of ‘mid’ using a loop.
Hence the time complexity will be O( n * log(M) )
O( 1 ).
In the above algorithm, we only use variables.
Hence the space complexity will be O( 1 ).
All tags
Sort by
Interview problems
Java simple solution using Binary Search
public class Solution {
public static int NthRoot(int n, int m) {
int s = 1;
int e = m;
while( e >= s ){
int mid = s+(e-s)/2;
long val = (long)Math.pow(mid,n);
if( val == m ) return mid;
if(val < m) s = mid+1;
else e = mid-1;
}
return -1;
}
}
Interview problems
CPP Best Solution
int func(int mid,int n,int m){
long long ans= 1;
for(int i=1;i<=n;i++){
if(ans*mid>m) return 0;
ans = ans * mid;
}
if(ans == m){
return 1;
}
return 2;
}
int NthRoot(int n, int m) {
// Write your code here.
int low = 1;
int high = m;
while(low<=high){
int mid = (low+high)/2;
int val = func(mid, n, m);
if(val==1){
return mid;
}else if(val == 0){
high = mid - 1;
}else{ low = mid + 1; }
}
return -1;
}
Interview problems
Always give priority to the datatypes that can occur in the middle of the calculations
int NthRoot(int n, int m) {
// Write your code here.
int ans = 0;
int st = 1, end = m;
while(st<=end){
long long int mid = st+(end-st)/2;
if(pow(mid, n) == m) return mid;
if(pow(mid, n)<m){
st = mid+1;
}
else {
end = mid-1;
}
}
return -1;
}
Interview problems
Binary solution C++
int NthRoot(int n, int m) {
// Write your code here.
int low=1,high=m;
while(low<=high){
int mid=(low+high)/2;
double cub=pow(mid,n);
if(cub==m) return mid;
else if(cub>m) high=mid-1;
else low=mid+1;
}
return -1;
}Interview problems
In java .... Round the ans and check again to verify
public class Solution {
public static int NthRoot(int n, int m) {
// Write your code here.
double root = Math.pow(m, 1.0 / n);
// Round the result and check if it's an integer
int roundedRoot = (int) Math.round(root);
// Verify if the rounded root raised to the power of n gives back m
if (Math.pow(roundedRoot, n) == m) {
return roundedRoot;
} else {
return -1;
}
}
}
Interview problems
Easy Solution in C++
#include <bits/stdc++.h>
int NthRoot(int n, int m) {
for(int i=1;i<sqrt(m);i++){
if(pow(i,n)==m){
return i;
}
if(pow(i,n)>m){
break;
}
}
return -1;
}
Interview problems
BETTER THAN 100% C++
#include <bits/stdc++.h>
using namespace std;
//return 1, if == m:
//return 0, if < m:
//return 2, if > m:
int func(int mid, int n, int m) {
long long ans = 1;
for (int i = 1; i <= n; i++) {
ans = ans * mid;
if (ans > m) return 2;
}
if (ans == m) return 1;
return 0;
}
int NthRoot(int n, int m) {
//Use Binary search on the answer space:
int low = 1, high = m;
while (low <= high) {
int mid = (low + high) / 2;
int midN = func(mid, n, m);
if (midN == 1) {
return mid;
}
else if (midN == 0) low = mid + 1;
else high = mid - 1;
}
return -1;
}
Interview problems
C++ Code Easy Binary Search Technique
// if(mid^n > number) return 0
// if(mid^n == number) return 1
// if(mid^n < number) return 2
int func (int mid , int n, int number){
long long ans = 1;
for(int i =0; i<n ;i++){
ans = ans*mid;
if(ans > number) return 0;
}
if(ans == number) return 1;
return 2;
}
int NthRoot(int power, int number){
int low = 1, high = number ;
while(low<=high){
int mid = (low+high)/2;
int midN = func(mid , power ,number);
if(midN == 1){
return mid;
}
else if(midN == 0){
high = mid-1;
}
else{
low = mid+1;
}
}
return -1;
}Interview problems
Find Nth Root Of M (Java) || time Complexity(log N x M) || Using Binary Search
public static int NthRoot(int n, int m) {
// Write your code here.
int start = 0;
int end = m;
while(start <= end){
int mid = start + (end - start)/2;
int pow =(int)Math.pow(mid, n);
if(pow == m){
return mid;
}else if(pow > m){
end = mid - 1;
}else{
start = mid + 1;
}
}return -1;
}
Interview problems
Java O(1) Solution✅
Using Mathematical properties of Log.
Considering ‘n’th root of ‘m’ means there exits a certain variable ‘a’ such that:
a^(n) = m
Applying Log on both sides:
log(a^n) = log(m)
Modifying it further gives us:
a = e^(log m / n)
which in code terms is represented as:
double a = Math.pow(Math.E, (Math.log(m)/n));
Then check for double infinitive and return int.
import java.util.*;
public class Solution {
public static int NthRoot(int n, int m) {
double a = Math.pow(Math.E, (Math.log(m)/n));
if (Math.ceil(a) - a < 0.000000001) return (int) Math.ceil(a);
else if (a - Math.floor(a) < 0.000000001) return (int) Math.floor(a);
if ((a == Math.floor(a)) && !Double.isInfinite(a)) {
return (int) a;
}
return -1;
}
}
