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

Enter fullscreen mode Exit fullscreen mode

Return:

x

Enter fullscreen mode Exit fullscreen mode

if it exists, otherwise return:

-1

Enter fullscreen mode Exit fullscreen mode

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;
    }
}

Enter fullscreen mode Exit fullscreen mode

Moving Towards the Optimal Approach

Notice:

If midⁿ < m

Enter fullscreen mode Exit fullscreen mode

then the answer must lie on the right.

And if:

midⁿ > m

Enter fullscreen mode Exit fullscreen mode

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]

Enter fullscreen mode Exit fullscreen mode

For every middle value:

midⁿ

Enter fullscreen mode Exit fullscreen mode

Compare with:

m

Enter fullscreen mode Exit fullscreen mode

Cases:

midⁿ == m → Found Answer

midⁿ < m  → Search Right

midⁿ > m  → Search Left

Enter fullscreen mode Exit fullscreen mode

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;
    }
}

Enter fullscreen mode Exit fullscreen mode

Dry Run

Input

n = 3
m = 27

Enter fullscreen mode Exit fullscreen mode

Iteration 1

low = 1
high = 27

mid = 14

14³ = 2744

Enter fullscreen mode Exit fullscreen mode

2744 > 27

Move Left

Enter fullscreen mode Exit fullscreen mode

Iteration 2

low = 1
high = 13

mid = 7

7³ = 343

Enter fullscreen mode Exit fullscreen mode

343 > 27

Move Left

Enter fullscreen mode Exit fullscreen mode

Iteration 3

low = 1
high = 6

mid = 3

3³ = 27

Enter fullscreen mode Exit fullscreen mode

Found Answer ✅

3

Enter fullscreen mode Exit fullscreen mode

Why Binary Search Works?

The function:

f(x) = xⁿ

Enter fullscreen mode Exit fullscreen mode

is monotonic increasing.

That means:

If x increases,
xⁿ also increases.

Enter fullscreen mode Exit fullscreen mode

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

Complexity Analysis

Metric Complexity Time Complexity O(log M × N) Space Complexity O(1)

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

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

Mental Model

Sorted Array
→ Binary Search on Index

Nth Root
→ Binary Search on Answer

Enter fullscreen mode Exit fullscreen mode

Whenever you hear:

“Find an exact root”

your brain should immediately think:

Binary Search on Answer Space