1343. The Integer kth Root
Print the largest integer r with r^k <= n. In other words, the kth root of
n rounded down.
n = 27, k = 3 -> 3
n = 28, k = 3 -> 3
n = 15, k = 4 -> 1
Calling a floating point power function is the tempting one-liner and it is not
reliable. n^(1/k) for n near 10^12 can land just below the true integer, and
rounding it sometimes fixes that and sometimes turns a correct 9999 into 10000.
Binary search instead, which is exact. The predicate r^k <= n is monotonic in
r: once it fails it fails for everything larger, so the search space splits
cleanly.
The trap is inside the predicate. Computing r^k directly overflows long before
r is anywhere near the answer, and the comparison then reads a wrapped value
and steers the search the wrong way. Multiply step by step and bail out the
moment the running product exceeds n:
p = 1
repeat k times:
if p > n / r: too big, stop
p = p * r
Dividing rather than multiplying to test keeps every intermediate value inside the range.
Constraints - `0 ≤ n ≤ 1000000000000` - `1 ≤ k ≤ 40`
Input
One line containing two integers n and k.
Output
Print the largest integer r with r raised to the power k at most n.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.