Given a positive integer n and a non-negative integer m, find the exact…
2026
Given a positive integer n and a non-negative integer m, find the exact integer nth root of m. Print -1 if no integer x satisfies xn = m.
Input format
One line containing two space-separated integers n and m.
Output format
Print the non-negative integer x when xn = m exactly; otherwise print -1.
Examples
Input | Output | Explanation |
|---|---|---|
3 8 | 2 | 2³ = 8 |
3 9 | -1 | No integer cube root of 9 exists. |
4 16 | 2 | 2⁴ = 16 |
Constraints
1 ≤ n ≤ 9
0 ≤ m ≤ 20
Attempted by 10 students.
Show answer & explanation
Concept
For non-negative integers, f(x) = xn is monotonic: increasing x never decreases the power.
Binary search can therefore test candidate roots from 0 through m. During a power test, stop multiplying as soon as the product exceeds m; this keeps the comparison exact and avoids unnecessary work.
Application
Read n and m. Set low = 0 and high = m.
While low ≤ high, choose mid = floor((low + high) / 2) and compute mid raised to n by repeated multiplication.
If the power equals m, print mid. If it is below m, set low = mid + 1; if it is above m, set high = mid - 1.
If the interval becomes empty, print -1 because no exact non-negative integer root exists.
Cross-check
Input | Observed search result | Output |
|---|---|---|
n = 3, m = 8 | The candidate 2 gives 2³ = 8. | 2 |
n = 3, m = 9 | No integer candidate has cube 9. | -1 |
The search uses O(log(m + 1)) iterations and at most n multiplications per power test, so the time complexity is O(n log(m + 1)) and the extra-space complexity is O(1).
Thus the method returns the exact non-negative integer nth root when it exists and -1 otherwise.