N-th Root of an Integer
Find the integer x with xⁿ = m, or report −1 if no exact integer root exists.
Intuition
xⁿ grows monotonically in x, and monotone means binary-searchable: guess a root, compare its n-th power to m, and discard half the candidates. This 'binary search on the answer' works whenever a yes/no test is monotone.
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
Search the answer space
Candidates are 1..m. For a guess mid, compare midⁿ with m — three-way: equal (found), less (go right), greater (go left).
Cap the power computation
Compute midⁿ with early exit once it exceeds m, so huge intermediate values never build up (matters in fixed-width languages).
No hit means no root
If the window empties, m isn't a perfect n-th power → −1.
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.