N-th Root of an Integer
Nth Root Of Integer: find the integer x with xⁿ = m, or report −1 if no exact integer root exists.
- 1 <= n <= 30
- 1 <= m <= 10⁹
- Return -1 when no exact integer root exists
Intuition
To find the n th root of an integer you need the whole number x with xⁿ = m, or −1 when no such integer exists. Testing every candidate from 1 upward works but is far too slow when m is large.
The property that rescues it is that xⁿ grows monotonically — as x increases, xⁿ only ever increases. That means a single guess tells you which direction to go: if midⁿ is below m, every candidate at or below mid is too small and can be discarded in one step.
Monotone comparisons are exactly what binary search needs, so search the answer space directly:
- Binary search over the candidate roots 1..m, not over any array.
This is the binary search on the answer pattern, and it applies whenever a yes/no test is monotone — the same idea behind Allocate Minimum Pages and Aggressive Cows.
One practical trap: computing midⁿ can overflow long before it ever reaches m. With m near a billion and n of 5, an early mid produces a number vastly larger than any fixed-width integer holds. So the power routine must stop multiplying as soon as the running product passes m — the exact value beyond that point is irrelevant, only the fact that it is too large.
Binary search on the answer, not on an array. Because x^n grows monotonically in x, the predicate "is x^n too big?" flips exactly once, which is all binary search needs. Whenever the answer is a number in a known range and you can test a guess more cheaply than deriving it, search the range — the same reflex solves koko-eating-bananas and split-array-largest-sum.
Approach
Before reading on: price up what the direct approach costs here, then ask what property lets you throw away half the range after one comparison. Aim for O(n log m) time and O(1) space.
Search the answer space, not an array
The candidates are the integers 1 through m. Set lo = 1 and hi = m, then binary search as normal. There is no array here — the thing being halved is the range of possible roots, which is what makes this the search-on-the-answer pattern.
Compare mid to the power, three ways
For a guess mid, compute midⁿ. If it equals m you have the exact root and can return immediately. If it is less than m, the root is larger, so move lo up. If greater, move hi down. Each comparison discards half the remaining candidates.
Cap the power computation
Multiply mid by itself n times but break the moment the running product exceeds m. Without this guard a large mid with a large n overflows a 64-bit integer and the comparison silently returns the wrong direction — a bug that only appears on big inputs.
An empty window means no exact root
If lo passes hi without an exact match, m is not a perfect n-th power. Return −1. The problem asks for an integer root, so a value between two candidates is not an answer.
Cost of the search
The candidate range halves each step, giving O(log m) iterations, and each does at most n multiplications with the early exit. That is O(n log m) time and O(1) space — a large improvement over scanning every candidate.
Solution & live demo
Common pitfalls
Computing the power without a cap
def power(x):
return x ** np = 1
for _ in range(n):
p *= x
if p > m: return pWith m near 10^9 and n large, the intermediate can reach astronomical sizes — slow in Python and an overflow in C++ or Java. Bailing out the moment the product exceeds m keeps every value bounded, and the exact magnitude beyond that never matters.
Using floating-point roots
r = round(m ** (1 / n)) return r if r ** n == m else -1
lo, hi = 1, m
while lo <= hi:
mid = (lo + hi) // 2
...m ** (1/n) carries rounding error that lands on the wrong integer for large inputs — a perfect cube can come back as x.9999999 and round down. Integer binary search is exact.
Returning the closest value instead of -1
return lo
return -1
The problem asks for an exact n-th root; when none exists the loop ends with lo and hi crossed around a non-solution. Returning lo reports a number whose n-th power isn't m.
Edge cases
1ⁿ = 1 for every n → answer 1.
Every m is its own first root — the search finds mid = m.