You are given two integers n and m. Your task is to find the nth root of m — the integer x such that x^n = m.
If no such integer exists (the root is not a whole number), return -1.
In other words: find x with x * x * ... * x (n times) exactly equal to m, or report that it is impossible.
27 can come out as 2.9999999999, and rounding the wrong way silently returns -1 for a perfect power. You would need to check the rounded value and its neighbors with exact integer math anyway — the integer binary search does that exactness natively.m. The partial product then never grows past m * mid, which fits comfortably in 64 bits.m = 1 returns 1 for every n, since 1^n = 1. n = 1 returns m itself, since m^1 = m. Both fall out naturally if your search range is [1, m].x^n strictly increases with x, comparing mid^n to m tells you which half of the candidate range survives — the sorted array is implicit.-1, track the last mid whose power was <= m (move lo up past it) and return that best-so-far when the range empties.O(n log m). Only the arithmetic care grows: keep the capped multiplication in 64-bit (or big-integer) types, and cap hi at something like 10^6–10^9 depending on n, since the root shrinks fast as n grows.x ← ((n-1)·x + m / x^(n-1)) / n and converges quadratically, which is how math libraries compute roots. In an interview, integer binary search is preferred: no convergence or precision arguments needed.Input: n = 3, m = 8 Output: 2 2^3 = 2 × 2 × 2 = 8, so the cube root of 8 is exactly 2.
Input: n = 3, m = 9 Output: -1 2^3 = 8 is too small and 3^3 = 27 is too big — no integer cubed gives 9.
Input: n = 4, m = 16 Output: 2 2^4 = 16, so the 4th root of 16 is exactly 2.
- 1 <= n <= 30 - 1 <= m <= 10^9
This problem looks like arithmetic, but it is really a search problem in disguise — and it is one of the cleanest introductions to binary search on the answer: searching a range of candidate values instead of an array.
1..m, not an array.x^n for growing x), one comparison tells you which half of the range still matters.mid^n can be astronomically large; you must stop multiplying the moment the partial product exceeds m.Plainly: we want an integer x with x^n = m. Formally, return x such that x^n = m if one exists, else -1. Because x^n strictly increases as x increases (for x >= 1), at most one such x exists — and the comparisons x^n < m, = m, > m split the candidates into a too small zone, (maybe) the answer, and a too big zone.
Worked example — n = 3, m = 64
candidates: 1 2 3 4 5 6 7 8 ... 64
x^3: 1 8 27 64 125 216 343 512
^
< 64 ──────┤├────── > 64
answer: 4 (4^3 = 64)
Asking two or three sharp questions before coding shows an interviewer you think about contracts, not just code.
“Can n be 1?”
Yes — then the answer is trivially m itself, since m^1 = m. A good branch to confirm rather than assume.
“Are n and m always positive?”
Here n >= 1 and m >= 1, so we never deal with roots of zero or negatives — that keeps x^n strictly increasing.
“What should I return for m = 1?”
1, for every n — since 1^n = 1. It is the smallest candidate, so make sure your search range includes it.
“What if the root exists but is not an integer, like the cube root of 9?”
Return -1. We only accept an exact integer root — no rounding.
“How large can m get?”
Up to 10^9. A linear scan of candidates is about sqrt(m) ≈ 31,623 steps at worst — passable here, but binary search in ~30 steps is the expected answer and scales to any m.
“Can computing mid to the power n overflow?”
Absolutely — 31623^30 is beyond any built-in integer type. The fix: multiply step by step and bail out the instant the running product exceeds m.
Before I code, a few clarifying questions.
Since n and m are both at least 1, x to the n is strictly increasing — so at most one integer root exists, correct?
If the root is not an exact integer, I return -1 rather than a floor or a rounded value?
And since mid to the power n can overflow, I will cap the multiplication early — stopping as soon as the partial product passes m.
For x >= 1, x^n strictly increases with x. So the sequence 1^n, 2^n, 3^n, … is a sorted, invisible array. We never need to build it — we can compute any entry on demand. A sorted space plus random access is the exact precondition for binary search.
Compare mid^n against m:
mid^n < m → every candidate ≤ mid is too small → lo = mid + 1 mid^n > m → every candidate ≥ mid is too big → hi = mid - 1 mid^n = m → found it — return mid
If the range empties without a hit, no integer root exists → -1.
mid^n can dwarf any integer type long before the loop ends (2^100 has 31 digits). But we only ever need to know how it compares to m (at most 10^9). So multiply one factor at a time, and the moment the running product exceeds m, stop — the verdict is already too big. The partial product stays small and overflow never happens.
| Linear scan | Binary search on answer | |
|---|---|---|
| Time | O(n · m^(1/n)) | O(n · log m) |
| Space | O(1) | O(1) |
| Steps for m = 10^9, n = 2 | ~31,623 candidates | ~30 probes |
Both approaches, with full code and traces, are in the Approaches selector below.
Key takeaway
When the answer lives on a monotonic scale — here, x^n only grows as x grows — binary search the answer's range directly instead of scanning it. This binary search on answer pattern is one of the most reusable ideas in interviews.
lo = 1, hi = m
while lo <= hi:
mid = (lo + hi) / 2
p = mid^n, capped: stop multiplying once p > m
if p == m: return mid
if p < m: lo = mid + 1
else: hi = mid - 1
return -1