Find Nth Root Of M

Problem statement

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. (link)

Note:

'nth' root of an integer 'm' is a number, which, when raised to the power 'n', gives 'm' as a result.

Example:

Input: ‘n’ = 3, ‘m’ = 27
Output: 3

Explanation: 
3rd Root of 27 is 3, as (3)^3 equals 27.

Sample Input 1: 3 27

Sample Output 1: 3

Explanation For Sample Input 1: 3rd Root of 27 is 3, as (3)^3 equals 27.

Sample Input 2: 4 69

Sample Output 2:- 1

Explanation For Sample Input 2: 4th Root of 69 is not an integer, hence -1.

Expected Time Complexity: Try to do this in O(log(n+m)).

Constraints:

1 <= n <= 30

1 <= m <= 10^9

Solution

Brute force Approach

We systematically examine each number starting from 1, calculating its nth power to find the nth root of a given number, m. If we find a number whose nth power matches the target value, we return that number. Otherwise, we continue checking each number to see if its nth power exceeds the target. If it does, we return -1.

public class Solution {

    public static int getTheNthPower(int mid, int n, int m){
        long pow = 1;
        for(int i=0; i<n; i++){
            pow*=mid;
        }
        return (int)pow;
    }

    public static int NthRoot(int n, int m) {

        for(int i=1; i<=m; i++){
            int pow = getTheNthPower(i, n, m);
            if(pow==m) return i;

            if(pow>m) return -1;
        }
        return -1;
    }
}

Optimal Approach - Binary Search

This method bears resemblance to the brute-force approach typically employed in solving problems like finding the square root of a number (referenced via the provided link). Utilizing a standard binary search, akin to how we tackle square root problems, we handle the computation of the nth power. Given the potential for overflow during power calculations, we employ a long data type and check if the result exceeds the target value, m. Upon exceeding, we return m+1, signifying that further power calculations are unnecessary. This action serves to eliminate the right half of the search space, as the power of the midpoint surpasses m.

public class Solution {

    public static int getTheNthPower(int mid, int n, int m){
        long pow = 1;
        for(int i=0; i<n; i++){
            if(pow*mid>m) return m+1;
            pow*=mid;
        }
        return (int)pow;
    }

    public static int NthRoot(int n, int m) {

        int low = 1;
        int high = m;

        while(low<=high){
            int mid = (low+high)/2;

            int nthPower = getTheNthPower(mid,n, m);

            if(nthPower==m) return mid;

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

Code Meditations