Topics › Binary Search › BS on Answers

Find Nth root of a number

Medium TUF ID 91 A2Z

Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given two positive integers n and m. Return the integer x such that x^n = m (the n-th root of m), if such an integer exists. If m has no exact integer n-th root, return -1.

Constraints: 1 ≤ n ≤ 30, 1 ≤ m ≤ 10^9.

Example 1

n = 3, m = 27
answer = 3          // 3 * 3 * 3 = 27

Example 2

n = 4, m = 69
answer = -1         // 2^4 = 16 < 69 < 81 = 3^4, no integer works

Example 3

n = 1, m = 14
answer = 14         // the first root of a number is the number itself

Compared with the square-root problem, two things change: the exponent is a parameter, and only an exact root counts, so “floor of the root” is not enough. The structure of the search is otherwise identical.

A helper that compares x^n with m safely

Computing x^n naively is dangerous. Even with x ≤ 10^9 and n ≤ 30, the true value of x^n can be astronomically large and overflows long after a few multiplications. We never actually need the value, only its relationship with m. So we multiply step by step and stop as soon as the running product exceeds m: once that happens, the final power is certainly larger than m too (because x ≥ 1, multiplying further never decreases the product). Before each multiplication the running product is at most m ≤ 10^9 and x ≤ 10^9, so the product fits comfortably in a long (at most about 10^18). The helper returns -1, 0 or 1 for “less than”, “equal to” and “greater than” m.

static int comparePower(int x, int n, int m) {
    long ans = 1;
    for (int i = 0; i < n; i++) {
        ans *= x;
        if (ans > m) return 1;    // already too big; with x >= 1 it can only grow further
    }
    return ans == m ? 0 : -1;
}

Both approaches below use this helper. Its cost is O(n) multiplications per call in the worst case.

Approach 1: Brute force, try every candidate

Intuition. Candidates for x are 1, 2, 3, .... Because x^n grows strictly with x, we can test each candidate in turn: if x^n == m we have the answer, if x^n > m no larger candidate can work and we can return -1 immediately, otherwise move on.

Algorithm.

1. For x = 1, 2, 3, ... up to m:
   • Let c = comparePower(x, n, m).
   • If c == 0, return x.
   • If c > 0, return -1.
2. Return -1 (only reached for inputs outside the constraints).

static int bruteForce(int n, int m) {
    for (int x = 1; x <= m; x++) {
        int c = comparePower(x, n, m);
        if (c == 0) return x;
        if (c > 0) return -1;     // x^n already exceeds m, so no larger x can work either
    }
    return -1;
}

Complexity. Time O(m^(1/n) * n): the loop stops once x passes the real n-th root of m, and each test costs up to n multiplications. For n = 2 that is about 31,623 * 2 operations, fine; for n = 1 it degenerates to O(m), which is 10^9 steps in the worst case and far too slow. Space O(1).

Approach 2: Optimal, binary search on the answer

Intuition. The comparison comparePower(x, n, m) is monotonic in x: it is -1 for all x below the real root, 0 at the exact root if one exists, and 1 for every x above. That is exactly the shape binary search needs. Pick the middle candidate: if its power is too small, every smaller candidate is also too small, so move lo up; if it is too large, move hi down; if it is equal, we are done. If the loop ends without a hit, the root is not an integer.

The search space is [1, m]. Any x > m has x^n ≥ x > m for n ≥ 1, so nothing is lost by stopping at m.

Algorithm.

1. Set lo = 1, hi = m.
2. While lo ≤ hi:
   • mid = lo + (hi - lo) / 2, c = comparePower(mid, n, m).
   • If c == 0, return mid.
   • If c < 0, set lo = mid + 1; else set hi = mid - 1.
3. Return -1.

static int optimal(int n, int m) {
    int lo = 1, hi = m;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        int c = comparePower(mid, n, m);
        if (c == 0) return mid;
        if (c < 0) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

Dry run on n = 3, m = 27:

And on n = 4, m = 69:

The loop exits with lo = 3 > hi = 2 and no exact hit, so the answer is -1.

Complexity. Time O(n log m): about log2(10^9) ≈ 30 iterations, each costing up to n ≤ 30 multiplications, under a thousand operations in total. Space O(1).

The early exit inside comparePower is what keeps the per-step cost small for large mid: a candidate like mid = 5 * 10^8 with n = 30 is rejected after the second multiplication.

Edge cases and pitfalls

• m = 1. 1^n = 1 for every n, so the answer is 1. The binary search has lo = hi = 1, tests mid = 1, and returns it.
• n = 1. The answer is m itself. The brute force would need m iterations; the binary search still takes about log m steps. This is the input that makes the brute force unacceptable.
• Overflow. mid^n overflows long for almost every mid when n is large. Never compute the full power; compare incrementally and bail out early as in comparePower. The Java test n = 30, m = 2^30 expects 2, and a naive int power would overflow for every mid ≥ 3.
• Returning floor instead of exact. n = 2, m = 10^9 has no integer root (31622^2 < 10^9 < 31623^2), so the answer is -1, not 31622. If your version of the problem asks for the floor, keep the same search but record the last mid whose power was ≤ m, as in the square-root problem.
• Choosing hi. hi = m is safe. A tighter bound such as the integer square root of m works only for n ≥ 2; keep hi = m so that n = 1 is handled uniformly.
• (lo + hi) / 2. Use lo + (hi - lo) / 2 to avoid overflow when hi is near Integer.MAX_VALUE; with m ≤ 10^9 the sum would fit, but the habit costs nothing.

Related problems

• Find square root of a number is the n = 2 case asking for the floor rather than an exact root.
• Koko eating bananas and Find the smallest divisor apply the same monotonic-predicate search to array-based conditions.
• Minimum days to make M bouquets adds the twist that the answer may not exist, mirroring the -1 case here.