N-th root of a number

Given two integers n and m, find the n-th root of m. The n-th root of m is an integer x such that x^n = m. If no such integer exists, return -1.

Examples:

Input: n = 3, m = 27
Output: 3
Explanation: 3³ = 27
Input: n = 3, m = 9
Output: -1
Explanation: 3rd root of 9 is not integer.

Try it on GfG Practice

Table of Content

[Approach 1] Using Binary Search - O(n * log(m)) Time and O(1) Space
[Approach 2] Using Newton's Method

[Approach 1] Using Binary Search - O(n * log(m)) Time and O(1) Space

The idea is to search within the range from 1 to m. In each step, we do the following

The middle value is raised to the power of n and compared to m. If it equals m, that value is the root.
If it is greater, the search continues in the lower half; if smaller, in the upper half.

This process repeats until the root is found or the range is exhausted. If no exact integer root exists, the function returns -1.

C++

#include <iostream>
#include <vector>
using namespace std;

// function to calculate base^expo 
// returns early if result exceeds the 
// given limit to avoid overflow
int power(int base, int expo, int limit) {
    int result = 1;
    for (int i = 0; i < expo; i++) {
        result *= base;
        
        if (result > limit)  
            return result;
    }
    return result;
}

// function to find the 
// n-th root of m
int nthRoot(int n, int m) {
    
    // n-th root of 0 is 0
    if (m == 0) return 0;

    // If n is 1, the answer 
    // is m itself
    if (n == 1) return m;

    // binary search to find 
    // the integer root
    int low = 1, high = m;
    while (low <= high) {
        int mid = (low + high) / 2;

        // compute mid^n and compare it with m
        int val = power(mid, n, m);

        if (val == m)
            return mid;  
        else if (val < m)
            low = mid + 1;  
        else
            high = mid - 1; 
    }

    return -1;
}

int main() {
    int n = 3, m = 27;  
    
    int result = nthRoot(n, m);
    cout << result << endl; 

    return 0;
}

Java

class GfG {

    // function to calculate base^expo 
    // returns early if result exceeds the 
    // given limit to avoid overflow
    static int power(int base, int expo, int limit) {
        int result = 1;
        for (int i = 0; i < expo; i++) {
            result *= base;
            
            if (result > limit)  
                return result;
        }
        return result;
    }

    // function to find the 
    // n-th root of m
    static int nthRoot(int n, int m) {
        // n-th root of 0 is 0
        if (m == 0) return 0;

        // If n is 1, the answer 
        // is m itself
        if (n == 1) return m;

        // binary search to find 
        // the integer root
        int low = 1, high = m;
        while (low <= high) {
            int mid = (low + high) / 2;

            // compute mid^n and compare it with m
            int val = power(mid, n, m);

            if (val == m)
                return mid;  
            else if (val < m)
                low = mid + 1;  
            else
                high = mid - 1; 
        }

        return -1;
    }

    public static void main(String[] args) {
        int n = 3, m = 27;  
        
        int result = nthRoot(n, m);
        System.out.println(result); 
    }
}

Python

# function to calculate base^expo 
# returns early if result exceeds the 
# given limit to avoid overflow
def power(base, expo, limit):
    result = 1
    for _ in range(expo):
        result *= base
        
        if result > limit:  
            return result
    return result

# function to find the 
# n-th root of m
def nthRoot(n, m):
    # n-th root of 0 is 0
    if m == 0:
        return 0

    # If n is 1, the answer 
    # is m itself
    if n == 1:
        return m

    # binary search to find 
    # the integer root
    low, high = 1, m
    while low <= high:
        mid = (low + high) // 2

        # compute mid^n and compare it with m
        val = power(mid, n, m)

        if val == m:
            return mid  
        elif val < m:
            low = mid + 1  
        else:
            high = mid - 1 

    return -1

if __name__ == "__main__":
    n = 3
    m = 27
    
    result = nthRoot(n, m)
    print(result)

using System;

class GfG{
    // function to calculate base^expo 
    // returns early if result exceeds the 
    // given limit to avoid overflow
    static int power(int baseVal, int expo, int limit){
        int result = 1;
        for (int i = 0; i < expo; i++){
            result *= baseVal;

            if (result > limit)
                return result;
        }
        return result;
    }

    // function to find the 
    // n-th root of m
    static int nthRoot(int n, int m){
        // n-th root of 0 is 0
        if (m == 0) return 0;

        // If n is 1, the answer 
        // is m itself
        if (n == 1) return m;

        // binary search to find 
        // the integer root
        int low = 1, high = m;
        while (low <= high){
            int mid = (low + high) / 2;

            // compute mid^n and compare it with m
            int val = power(mid, n, m);

            if (val == m)
                return mid;
            else if (val < m)
                low = mid + 1;
            else
                high = mid - 1;
        }

        return -1;
    }

    static void Main(string[] args){
        int n = 3, m = 27;

        int result = nthRoot(n, m);
        Console.WriteLine(result);
    }
}

JavaScript

// function to calculate base^expo
// returns early if result exceeds the 
// given limit to avoid overflow
function power(base, expo, limit) {
    let result = 1;
    for (let i = 0; i < expo; i++) {
        result *= base;

        if (result > limit)
            return result;
    }
    return result;
}

// function to find the 
// n-th root of m
function nthRoot(n, m) {
    // n-th root of 0 is 0
    if (m === 0) return 0;

    // If n is 1, the answer 
    // is m itself
    if (n === 1) return m;

    // binary search to find 
    // the integer root
    let low = 1, high = m;
    while (low <= high) {
        let mid = Math.floor((low + high) / 2);

        // compute mid^n and compare it with m
        let val = power(mid, n, m);

        if (val === m)
            return mid;
        else if (val < m)
            low = mid + 1;
        else
            high = mid - 1;
    }

    return -1;
}

// Driver Code
const n = 3, m = 27;

const result = nthRoot(n, m);
console.log(result);

Output

[Approach 2] Using Newton's Method

This problem involves finding the real-valued function A^{1/N}, which can be solved using Newton's method. The method begins with an initial guess and iteratively refines the result.

By applying Newton's method, we derive a relation between consecutive iterations:

According to Newton's method:

\frac{f(x_k)}{f'(x_k)}

Here, we define the function f(x) as:

f(x) = x^N- A

The derivative of f(x), denoted f'(x), is:

N\cdot x^{N - 1}

The value x_k represents the approximation at the k-th iteration. By substituting f(x) and f'(x) into the Newton's method formula, we obtain the following update relation:

\frac{1}{N} \left( (N - 1) \cdot x_k + \frac{A}{x_k^{N - 1}} \right)

Using this relation, the problem can be solved by iterating over successive values of x until the difference between consecutive iterations is smaller than the desired accuracy.

Note: The code below returns the approx value so we use the check to find the if the real nth root is exact.

C++

#include <iostream>
#include <cmath>
#include <cstdlib>
#include <climits>
using namespace std;

int nthRoot(int m, int n) {
    if (n == 1) {
        return m;
    }

    double xPre = rand() % 10 + 1;

    // Smaller eps denotes more accuracy
    double eps = 1e-3;

    // Initializing difference 
    // between two roots
    double delX = INT_MAX;

    // xK denotes current value of x
    double xK;

    // Loop until we reach the 
    // desired accuracy
    while (delX > eps) {
        // Calculating the current value from 
        // the previous value by Newton's method
        xK = ((n - 1.0) * xPre + (double)m / pow(xPre, n - 1)) / (double)n;
        delX = abs(xK - xPre);
        xPre = xK;
    }

    return (int)round(xK);
}

// Function to check if rootCandidate 
// is exactly the nth root of m
int check(int m, int n, int rootCandidate) {
    int result = 1;
    for (int i = 0; i < n; i++) {
        // Detect overflow
        if (abs(result) > INT_MAX / abs(rootCandidate)) {
            
            // overflow means it's not a valid perfect root
            return -1; 
        }
        result *= rootCandidate;
    }
    return (result == m) ? rootCandidate : -1;
}

int main() {
    int n = 3, m = 27;

    int nthRootValue = nthRoot(m, n);
    int verifiedValue = check(m, n, nthRootValue);

    cout << verifiedValue << endl;

    return 0;
}