The challenge
Return an integer r with rᵖ = x, or −1 if no exact nonnegative integer root exists.
0 ≤ x ≤ 10⁹ and 1 ≤ p ≤ 31. Return 0 for x = 0.
Example
x = 27, p = 3 → 3; x = 28, p = 3 → −1.
Use the walkthrough below to inspect the input and each state change.
See Nth root, step by step
Inspect the comparison, the invariant, and the next boundary.
Answer-space searchx = 27 · p = 3
Tested candidate / qualifying inputResolved positionParameters shown above
- Left
- 1
- Middle
- —
- Right
- 27
Step 01 / 5
Search the answer range
The candidate is a number, rather than an input index. Require an exact power match.
left = 1; right = 27Recorded result so far
Not resolved
View exact input
Input: [] · x = 27 · p = 3
Put it into code
Binary search candidate roots. Build the power with a guard before every multiplication and stop as soon as it would exceed x.
Indices are zero-based. C++ uses C++17 or later.
def nth_root(x, p):
# 0 <= x <= 10**9; 1 <= p <= 31.
if x == 0:
return 0
left, right = 1, x
while left <= right:
mid = left + (right - left) // 2
power = 1
for _ in range(p):
if power > x // mid:
power = x + 1
break
power *= mid
if power == x:
return mid
if power < x:
left = mid + 1
else:
right = mid - 1
return -1long long nth_root(long long x, int p) {
if (x == 0) return 0;
long long left = 1, right = x;
while (left <= right) {
long long mid = left + (right - left) / 2, power = 1;
for (int i = 0; i < p; ++i) {
if (power > x / mid) { power = x + 1; break; }
power *= mid;
}
if (power == x) return mid;
if (power < x) left = mid + 1;
else right = mid - 1;
}
return -1;
}