1400. The Cube Root, Rounded Down, Either Sign
For each query print the largest integer r with r * r * r <= n. The value
n may be negative.
n = 8 -> 2 since 2^3 = 8
n = 9 -> 2 since 2^3 = 8 <= 9 and 3^3 = 27 > 9
n = -8 -> -2 since (-2)^3 = -8
n = -9 -> -3 since (-3)^3 = -27 <= -9 and (-2)^3 = -8 > -9
n = 0 -> 0
Read the negative case carefully, because it is the point of the problem. The answer is the cube root rounded down, not rounded toward zero. The real cube root of -9 is about -2.08, and rounding that down gives -3.
## What most people try first
(long long) cbrt(n), or pow(n, 1.0/3.0) with a sign fix. Both fail twice
over. A double has 53 bits of mantissa while |n| reaches 10^18, so the
library root can land on either side of the truth next to a perfect cube, and
pow of a negative base is not defined at all in several of these languages.
Rounding the result does not help, because the question asks for a floor and
the library gives a nearest value.
## One search over the whole range, signs included
r -> r^3 is strictly increasing over all integers, negative ones
included, which is exactly what makes a single search work with no sign
analysis. Since |n| <= 10^18, the answer lies in [-10^6, 10^6], so search
that fixed range for the largest r whose cube does not exceed n:
lo = -1000001, hi = 1000001
while lo < hi:
mid = lo + (hi - lo + 1) / 2
if mid^3 <= n: lo = mid
else: hi = mid - 1
answer = lo
## Why it is correct
The predicate r^3 <= n is monotone: true for every r at or below the
answer, false above it, because cubing preserves order on the integers. A
binary search on a monotone predicate converges on the boundary, and the
invariant maintained here is that lo^3 <= n always holds while hi is
always at or above the answer, so when they meet the common value is the
answer. Taking mid as the upper of the two middles is what guarantees
progress when hi = lo + 1.
## The boundary that breaks a careless implementation
Writing the midpoint as (lo + hi + 1) / 2 is wrong here, and silently so.
With lo = -5 and hi = -4 the sum is -8, and Python floors -8 / 2 to -4
while C and Java truncate toward zero, also to -4; but with lo = -5 and
hi = -3 the sum is -7, and Python gives -4 while C and Java give -3. The
two conventions genuinely differ on negative operands. Writing
lo + (hi - lo + 1) / 2 keeps the divided quantity positive, so all five
languages agree, and that is why every reference here is written that way.
## Overflow
|n| reaches 10^18, which needs 64 bits; a signed 32-bit integer stops at
2147483647 and cannot even hold the input. The cube mid * mid * mid with
|mid| up to 1000001 reaches about 10^18, which still fits a signed 64-bit
integer, whose limit is 9223372036854775807. In JavaScript 10^18 is past
2^53, so the search is done in BigInt.
## Cost
O(log(10^6)) per query, about 21 steps.
Constraints - `1 ≤ q ≤ 100` - `-1000000000000000000 ≤ n ≤ 1000000000000000000`
Input
The first line contains q.
The next q integers are the values n, and may be laid out one per line or
several to a line.
Output
For each query print the largest integer whose cube does not exceed n, one
per line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.