AlgoViz
HomeBinary Search

Find Nth root of a number

Medium

Same boundary search, with a power

Problem

Given two numbers N and M, find the Nth root of M. The Nth root of a number M is defined as a number X such that when X is raised to the power of N, it equals M. If the Nth root is not an integer, return -1.

In simple words

Binary-search a base whose n-th power hits m; if none lands exactly, answer -1.

The idea

k^n grows monotonically in k, so binary search k and compare k^n against m. Cap the multiplication as soon as it exceeds m so huge intermediate values never appear.

The trick

  • Stop multiplying the moment the running power passes m.
  • Return -1 when no k gives exactly m.
  • O(n log m) with the bounded power check.
1
2
3
4
0
1
2
3

Step 1 of 5. Brute force: try 1, 2, 3, … until kⁿ reaches 27. Values: 1, 2, 3, 4.

1/5
Brute force
timeO(m)spaceO(1)

Count up.

1let k = 1;2while (Math.pow(k, n) < m) k++;3const exact = Math.pow(k, n) === m;4return exact ? k : -1;

Input

array
[1, 2, 3, 4]

Memory

k
—

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
n = 3, m = 27
Output:
3
Explanation:
3^3 = 27 exactly.

Example 2

Input:
n = 4, m = 69
Output:
-1
Explanation:
No integer 4th root of 69 → -1.

Example 3

Input:
n = 2, m = 49
Output:
7
Explanation:
7^2 = 49.

Constraints

  • 1 <= N <= 30
  • 1 <= M <= 10^9

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.