N-th Root of an Integer
Find the integer x with xⁿ = m, or report −1 if no exact integer root exists.
02
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.
03
Approach
1
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).
2
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).
3
No hit means no root
If the window empties, m isn't a perfect n-th power → −1.
04
Solution & live demo
python
▶1def nth_root(n, m):
▶2 def power(x): # x^n, capped just above m
▶3 p = 1
▶4 for _ in range(n):
▶5 p *= x
▶6 if p > m: return p
▶7 return p
▶8 lo, hi = 1, m
▶9 while lo <= hi:
▶10 mid = (lo + hi) // 2
▶11 p = power(mid)
▶12 if p == m: return mid
▶13 if p < m: lo = mid + 1
▶14 else: hi = mid - 1
▶15 return -1
05
Edge cases
m = 1
1ⁿ = 1 for every n → answer 1.
n = 1
Every m is its own first root — the search finds mid = m.
06
Complexity
Time
O(n log m)
Space
O(1)
log m guesses × O(n) power each.