Find Nth Root of a Number

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 such that when X is raised to the power of N, it equals M. If the Nth root is not an integer, return -1.

Examples

Example 1:

Input: N = 3, M = 27
Output: 3

Explanation: The cube root of 27 is equal to 3.

Example 2:

Input: N = 4, M = 69
Output: -1

Explanation: The 4th root of 69 does not exist. So, the answer is -1.

Example 3:

Input: N = 4, M = 81
Output: 3

Explanation: Because 3 * 3 * 3 * 3 = 81.

Constraints:

• 1 ≤ N ≤ 30
• 1 ≤ M ≤ 10^9

Different Approaches

1️⃣ Brute Force Approach

Intuition:

Perform a simple linear search in range[1, n]. Calculate the value of x raised to the power n for every number in the range. If it is equal to given number then x is the nth root of the number. If no such number (x) exists, return -1 as an answer.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    /* Function to calculate power using
    exponentiation by squaring method*/
    long long func(int b, int exp) {
        long long ans = 1;
        long long base = b;
        
        // Exponentiation by squaring method
        while (exp > 0) {
            if (exp % 2) {
                exp--;
                ans = ans * base;
            } else {
                exp /= 2;
                base = base * base;
            }
        }
        return ans;
    }
public:
    /* Function to find the nth root
    of m using linear search*/
    int NthRoot(int N, int M) {
        // Linear search on the answer space
        for (int i = 1; i <= M; i++) {
            long long val = func(i, N);
            
            /* Check if the computed
            value is equal to M */
            if (val == M * 1ll) {
                // Return the root value
                return i; 
            } else if (val > M * 1ll) {
                break;
            }
        }
        // Return -1 if no root found
        return -1; 
    }
};

int main() {
    int n = 3, m = 27;
    
    // Create an object of the Solution class
    Solution sol;
    
    int ans = sol.NthRoot(n, m);
    
    // Print the result
    cout << "The answer is: " << ans << "\n";
    
    return 0;
}

Complexity Analysis:

• Time Complexity: O(N), where N is the given number. Since we are using linear search, we traverse the entire answer space.
• Space Complexity: As no additional space is used, so the Space Complexity is O(1).

2️⃣ Binary Search

The idea here is to use binary search to optimize the solution. Although the traditional application of binary search involves a sorted array, upon clear observation, one can notice that the search space for the answer here ranges from 1 to n, which inherently forms a sorted sequence . So, binary search can be applied.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    /* Helper function to check the power of mid 
    with respect to m Returns: 1 - if mid^n == m,
    0 - if mid^n < m and 2 - if mid^n > m */
    int func(int mid, int n, int m) {
        long long ans = 1;
        for (int i = 1; i <= n; i++) {
            ans *= mid;
            // This is to handle overflow in multiplication
            if (ans > m) return 2;
        }
        if (ans == m) return 1;
        return 0;
    }
public:
    /* Function to find the nth root
    root of m using binary search*/
    int NthRoot(int N, int M) {
        // 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 if mid^N== M
                return mid;
            } 
            else if (midN == 0) {
                // Move to the right half if mid^N < M
                low = mid + 1;
            } 
            else {
                // Move to the left half if mid^N > M
                high = mid - 1;
            }
        }
        // Return -1 if no nth root found
        return -1;
    }
};

int main() {
    int n = 3, m = 27;
    
    // Create an object of the Solution class
    Solution sol;
    
    int ans = sol.NthRoot(n, m);
    
    // Print the result
    cout << "The answer is: " << ans << "\n";
    
    return 0;
}

Complexity Analysis:

• Time Complexity: O(logN), N is the given number. We are basically using binary search to find the minimum.
• Space Complexity: As no additional space is used, so the Space Complexity is O(1).