thesarfo

Reference

Nth Root of a Number

Finding the integer nth root of a number (or -1 if none exists) with linear search vs. binary search.

views 0

Find m^(1/n) if it’s an integer, else -1. n=3, m=27 → 3 (since 3^3 = 27).

Brute force: loop i from 1, compute i^n, compare to m.

public int nthRoot(int n, int m) {
    for (int i = 1; i <= m; i++) {
        double power = Math.pow(i, n);


        if (power == m) {
            return i;
        } else if (power > m) {
            break;
        }
    }
    return -1;
}

Optimal — binary search over [1, m], comparing mid^n to m:

public int nthRoot(int n, int m) {
    int low = 1, high = m;


    while (low <= high) {
        int mid = (low + high) / 2;
        double power = Math.pow(mid, n);


        if (power == m) {
            return mid;
        } else if (power > m) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -1;
}