Nth Root of a Number using Binary Search - Data Structure

Problem Statement: Given two numbers N and M, find the Nth root of M.

The nth root of a number M is defined as a number X when raised to the power N equals M.

Example 1:

Input: N=3 M=27

Output: 3

Explanation: The cube root of 27 is 3.

Example 2:

Input: N=2 M=16

Output: 4

Explanation: The square root of 16 is 4

Example 3:

Input: N=5 M=243

Output: 3

Explaination: The 5th root of 243 is 3

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution:

Nth root of a number M is defined as a number X when raised to the power N equals to M.

Approach: In order to find the Nth root of any given integer we are gonna use Binary Search.

Step 1: Take low and high. Low will be equal to 1 and high will be M. We will take the mid of low and high such that the searching space is reduced using low + high / 2.

Step 2: Make a separate function to multiply mid N times.

Step 3: Run the while loop till (high – low > eps). Take eps as 1e-6, since we have to find answers to 6 decimal places.

Step 4: If the mid is less than M, then we will reduce search space to low and mid. Else, if it is greater than M then search space will be reduced to mid and high.

Step 5: After the loop breaks we will have our answer as low or high.

We have to find the answer to 6 decimals. So, we will have a double 1e-6. We will run the while loop till (high – low > eps). When we will come out of the loop we will have the answer which will be equal to low as well as high.

Code:

C++ Code

#include <bits/stdc++.h>
using namespace std;
double multiply(double number, int n) {
    double ans = 1.0;
    for(int i = 1;i<=n;i++) {
        ans = ans * number;
    }
    return ans; 
}

void getNthRoot(int n, int m) {
    double low = 1;
    double high = m;
    double eps = 1e-7; 
    
    while((high - low) > eps) {
        double mid = (low + high) / 2.0; 
        if(multiply(mid, n) < m) {
            low = mid; 
        }
        else {
            high = mid; 
        }
    }
    
    cout <<n<<"th root of "<<m<<" is "<<low<<endl; 
    
}
int main() {
	int n=3, m=27; 
	getNthRoot(n, m); 
	return 0;
}

Output: 3th root of 27 is 3

Time Complexity: N x log(M x 10^d)

Space Complexity: O(1)

Java Code

import java.io.*;
class GFG {
    private static double multiply(double number, int n) {
        double ans = 1.0;
        for(int i = 1;i<=n;i++) {
            ans = ans * number;
        }
        return ans; 
    }
    private static void getNthRoot(int n, int m) {
        double low = 1;
        double high = m;
        double eps = 1e-7; 
        
        while((high - low) > eps) {
            double mid = (low + high) / 2.0; 
            if(multiply(mid, n) < m) {
                low = mid; 
            }
            else {
                high = mid; 
            }
        }
        
        System.out.println(n+"th root of "+m+" is "+low);  
        
    }
	public static void main (String[] args) {
		int n = 3, m = 27; 
		getNthRoot(n, m); 
	}
}

Output: 3th root of 27 is 3

Time Complexity: N x log(M x 10^d)

Space Complexity: O(1)

Python Code

def multiply(number, n):
    ans = 1.0
    for i in range(1, n + 1):
        ans = ans * number
    return ans




def getNthRoot(n, m):
    low = 1
    high = m
    eps = 1e-7


    while (high - low) > eps:
        mid = (low + high) / 2.0
        if multiply(mid, n) < m:
            low = mid
        else:
            high = mid


    print(n, "th root of ", m, " is ", low)




n = 3
m = 27
getNthRoot(n, m)

Output: 3th root of 27 is 3

Time Complexity: N x log(M x 10^d)

Space Complexity: O(1)

Special thanks to Rushikesh Adhav and Sudip Ghosh for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article