Find Nth root of m

Problem Link

find-nth-root-of-m

Problem Statement

You are given two integers n and m. Your task is to find the n-th root of m, i.e., find an integer x such that:

x^n == m

If no such integer exists (i.e., the n-th root is not a whole number), return -1.

Examples

• Input: n = 2, m = 9
  Output: 3
  Explanation: 3² = 9, so the square root of 9 is 3.

• Input: n = 3, m = 9
  Output: -1
  Explanation: Cube root of 9 is not an integer.

• Input: n = 1, m = 14
  Output: 14
  Explanation: Every number is its own 1st root.

Constraints

• 1 ≤ n ≤ 30

• 1 ≤ m ≤ 10^9

Intuition

This problem is essentially checking whether a number x exists such that:

x^n == m

Since the function x^n is monotonically increasing for positive integers x, binary search is an optimal way to find such an integer root.

We do not use built-in functions like Math.pow due to possible floating-point inaccuracies or overflows. Instead, we perform manual exponentiation with overflow checks.

Approach

1. Search Range:

   • We search for x in the range [1, m] because m is the maximum candidate that could satisfy x^n = m.

2. Binary Search:

   • Let start = 1, end = m.

   • While start <= end:

     • Calculate mid = (start + end) / 2

     • Compute mid^n without overflow using a helper method.

     • If mid^n == m, return mid

     • If mid^n > m, discard right half (end = mid - 1)

     • If mid^n < m, discard left half (start = mid + 1)

3. If no integer x satisfies x^n == m, return -1.

Java Code

class Solution {
    public int nthRoot(int n, int m) {
        int start = 1;
        int end = m;

        while (start <= end) {
            int mid = start + (end - start) / 2;
            int result = compare(mid, n, m);

            if (result == 1) {
                return mid; // mid^n == m
            } else if (result == 0) {
                end = mid - 1; // mid^n > m
            } else {
                start = mid + 1; // mid^n < m
            }
        }

        return -1; // No integer root
    }

    private int compare(int base, int exp, int target) {
        long result = 1;
        for (int i = 1; i <= exp; i++) {
            result *= base;
            if (result > target) return 0; // overflow or too big
        }
        if (result == target) return 1;
        return 2; // result < target
    }
}

Time and Space Complexity

• Time Complexity: O(log m * n)

  • Binary search runs in O(log m) iterations.

  • Each iteration checks mid^n using O(n) time.

• Space Complexity: O(1)

  • Only constant extra space is used.

Dry Run

Input:

n = 3, m = 27

Steps:

• start = 1, end = 27

• mid = 14 → 14^3 = 2744 → too large → end = 13

• mid = 7 → 7^3 = 343 → too large → end = 6

• mid = 3 → 3^3 = 27 → match found → return 3

Output:

3

Conclusion

This problem is a classic application of binary search on a monotonically increasing function (i.e., x^n). It teaches how to perform high-precision exponential calculations without overflow using long and custom logic.

This approach avoids relying on floating-point math, ensuring exactness for integer-based root calculations in constrained systems or coding interviews.