☕ DSA Java Articles

Topics › Binary Search › BS on Answers

The N-th root of an integer

Medium TUF ID 2771 SDE

Java source ↗ Edit this article ↗

Problem

You are given two positive integers n and m. Return the integer x such that x^n = m, that is, the n-th root of m. If no integer has this property, return -1.

The original SDE sheet video for this row asks a slightly different question: compute the real n-th root of m correct to 6 decimal places. The same idea solves both, so the article covers the integer version first and the real-valued version at the end.

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, so no integer works

Example 3

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

Approach 1: Brute force, try every candidate

Intuition. For x ≥ 1 and n ≥ 1, the function x^n is strictly increasing: a bigger base always gives a bigger power. So we can walk x = 1, 2, 3, ... and stop at the first x whose power reaches or passes m. If it lands exactly on m, that x is the root. If it jumps past m, every later x overshoots even more, so no integer root exists.

Both approaches need to compare x^n with m, and that comparison hides the real trap of this problem: x^n overflows almost immediately. With x = 1000 and n = 30 the true power has 91 digits. The helper below multiplies one factor at a time in long and gives up as soon as the running product exceeds m. Before each multiplication the product is at most m ≤ 10^9 and x ≤ 10^9, so the product never exceeds 10^18, which fits in a long.

static int comparePower(long x, int n, long m) {
    long result = 1;
    for (int i = 0; i < n; i++) {
        result *= x;
        if (result > m) return 1;                 // stop early: one more multiplication could overflow
    }
    return result == m ? 0 : -1;
}

Algorithm.

  1. For x = 1, 2, 3, ...: compare x^n with m.
  2. If they are equal, return x.
  3. If x^n > m, return -1.
static int bruteForce(int n, int m) {
    for (long x = 1; ; x++) {
        int c = comparePower(x, n, m);
        if (c == 0) return (int) x;
        if (c > 0) return -1;                     // x^n jumped past m, so no integer root exists
    }
}

Complexity. Time O(n · m^(1/n)): we stop once x reaches about m^(1/n), and each comparison costs up to n multiplications. Space O(1).

That bound looks small for large n, but the worst case is n = 1, where the loop walks all the way to m: a billion iterations for m = 10^9. For n = 2 it is about 31,623 iterations, which is fine. We want something that does not depend on m^(1/n) at all.

Approach 2: Optimal, binary search on the answer

Intuition. The monotonicity we used to stop the scan early is exactly what binary search needs. Over the candidates 1..m, the comparison x^n vs m reads “smaller, smaller, …, (maybe equal), bigger, bigger”. Look at the middle candidate: if its power is too small, the root (if any) is to the right; if too big, it is to the left. Each probe throws away half of the remaining candidates.

Why is m a safe upper bound? For x ≥ 2, x^n ≥ x, so any root of m is at most m. For m = 1 the root is 1, which is also inside [1, m].

Algorithm.

  1. Set lo = 1, hi = m.
  2. While lo ≤ hi: let mid = lo + (hi - lo) / 2 and compare mid^n with m.
    • Equal: return mid.
    • Smaller: the root must be bigger, so lo = mid + 1.
    • Bigger: the root must be smaller, so hi = mid - 1.
  3. If the range empties, no integer root exists: return -1.
static int optimal(int n, int m) {
    long lo = 1, hi = m;
    while (lo <= hi) {
        long mid = lo + (hi - lo) / 2;
        int c = comparePower(mid, n, m);
        if (c == 0) return (int) mid;
        if (c < 0) lo = mid + 1; else hi = mid - 1;
    }
    return -1;
}

Dry run on Example 2, n = 4, m = 69:

lo hi mid mid^4 vs 69 action
1 69 35 bigger hi = 34
1 34 17 bigger hi = 16
1 16 8 bigger (4096) hi = 7
1 7 4 bigger (256) hi = 3
1 3 2 smaller (16) lo = 3
3 3 3 bigger (81) hi = 2
3 2   range empty return -1

Notice that comparePower(35, 4, 69) stops after two multiplications (35 · 35 = 1225 > 69), so the huge candidates near the top of the range cost almost nothing.

Complexity. Time O(n log m): about log2(10^9) ≈ 30 probes, each with at most n multiplications. Space O(1).

Variant: the real-valued n-th root

When the problem asks for the real root to 6 decimal places, the candidates are no longer integers, but the shape of the argument is the same: x^n is still increasing on [0, ∞), so we can bisect the interval [0, max(1, m)]. If mid^n < m the root lies in the right half, otherwise in the left half.

Two details change with doubles. First, there is no “equal” case to stop on, and lo == hi may never happen because of rounding. A fixed number of halvings is the robust stopping rule: 100 halvings shrink an interval of length 10^9 by a factor of 2^100 ≈ 10^30, far below 10^-6 and in fact below the spacing of double values. (Looping while (hi - lo > 1e-7) also works.) Second, the product can overflow to Infinity for large mid and n. That is harmless here: Infinity < m is false, so the search correctly moves left.

static double realRoot(int n, int m) {
    double lo = 0, hi = Math.max(1.0, m);         // the root of m >= 0 lies in [0, max(1, m)]
    for (int iter = 0; iter < 100; iter++) {
        double mid = (lo + hi) / 2, p = 1;
        for (int i = 0; i < n; i++) p *= mid;
        if (p < m) lo = mid; else hi = mid;
    }
    return hi;
}

Complexity. Time O(100 · n), which is O(n) with a large constant. Space O(1).

Why not just call Math.pow(m, 1.0 / n) and round? For the real-valued version that is a fine one-liner. For the integer version it is a classic bug: in Java Math.pow(64, 1.0 / 3) evaluates to 3.9999999999999996, so casting to int gives 3 and you would wrongly report that 64 has no integer cube root. Exact integer arithmetic, as in comparePower, avoids the question entirely.

Edge cases and pitfalls