N-th root of a number | Binary Search on Answer

N-th root of a number - GeeksforGeeks

Your All-in-One Learning Portal: GeeksforGeeks is a comprehensive educational platform that empowers learners across domains-spanning computer science and programming, school education, upskilling, commerce, software tools, competitive exams, and more.

geeksforgeeks.org

Problem Statement

Given two integers:

• n → root value
• m → number

Find the integer x such that:

xⁿ = m

Return:

x

if it exists, otherwise return:

-1

Brute Force Intuition

In an interview, you can explain it like this:

We can try every number from 1 to m and calculate its nth power. If any number's nth power becomes equal to m, we have found our answer. Although straightforward, it unnecessarily checks many values.

Complexity

• Time Complexity: O(M × N)
• Space Complexity: O(1)

Brute Force Code

class Solution {

    public int nthRoot(int n, int m) {

        for (int i = 1; i <= m; i++) {

            long value = 1;

            for (int j = 0; j < n; j++) {
                value *= i;
            }

            if (value == m)
                return i;
        }

        return -1;
    }
}

Moving Towards the Optimal Approach

Notice:

If midⁿ < m

then the answer must lie on the right.

And if:

midⁿ > m

the answer must lie on the left.

This is exactly the Binary Search pattern.

Instead of searching indices, we are searching the answer itself.

Pattern Recognition

Whenever you see:

• Find minimum/maximum possible answer
• Answer lies in a range
• Monotonic behaviour

Think:

Binary Search on Answer

Optimal Approach

Search in the range:

[1, m]

For every middle value:

midⁿ

Compare with:

m

Cases:

midⁿ == m → Found Answer

midⁿ < m  → Search Right

midⁿ > m  → Search Left

Optimal Java Solution

class Solution {

    public int nthRoot(int n, int m) {

        int low = 1;
        int high = m;

        while (low <= high) {

            int mid = low + (high - low) / 2;

            long value = power(mid, n);

            if (value == m)
                return mid;

            if (value < m)
                low = mid + 1;
            else
                high = mid - 1;
        }

        return -1;
    }

    private long power(long base, int n) {

        long ans = 1;

        for (int i = 0; i < n; i++) {

            ans *= base;

            if (ans > Integer.MAX_VALUE)
                return ans;
        }

        return ans;
    }
}

Dry Run

Input

n = 3
m = 27

Iteration 1

low = 1
high = 27

mid = 14

14³ = 2744

2744 > 27

Move Left

Iteration 2

low = 1
high = 13

mid = 7

7³ = 343

343 > 27

Move Left

Iteration 3

low = 1
high = 6

mid = 3

3³ = 27

Found Answer ✅

3

Why Binary Search Works?

The function:

f(x) = xⁿ

is monotonic increasing.

That means:

If x increases,
xⁿ also increases.

So we can safely eliminate half of the search space every time.

Complexity Analysis

Where:

• log M comes from Binary Search.
• N comes from calculating midⁿ.

Interview One-Liner

Since xⁿ increases monotonically with x, we can binary search the answer space and compare midⁿ with m.

Pattern Learned

Answer Lies in a Range
+
Monotonic Function

=> Binary Search on Answer

Similar Problems

• Nth Root of a Number
• Square Root of X
• Koko Eating Bananas
• Minimum Days to Make Bouquets
• Capacity to Ship Packages
• Aggressive Cows

Memory Trick

Think:

midⁿ

Less than m ?
→ Go Right

Greater than m ?
→ Go Left

Equal ?
→ Answer Found

Mental Model

Sorted Array
→ Binary Search on Index

Nth Root
→ Binary Search on Answer

Whenever you hear:

"Find an exact root"

your brain should immediately think:

Binary Search on Answer Space