1342. Sum of the First n Cubes
Print 1^3 + 2^3 + ... + n^3. With n = 0 the sum is 0.
A loop is correct and runs in O(n). There is a closed form that runs in O(1)
and is one of the prettiest identities in elementary mathematics:
1^3 + 2^3 + ... + n^3 = ( n(n+1)/2 )^2
The sum of the first n cubes is the SQUARE of the sum of the first n numbers.
The whole difficulty is that the answer is enormous. At the stated maximum it is
just under 9.22 * 10^18, which is the edge of a signed 64-bit integer, so the
bound was chosen to sit exactly there and anything larger would not be
representable at all.
That makes the order of operations matter. Compute n(n+1)/2 FIRST and square
the result. Squaring n(n+1) before halving overflows at a quarter of the range,
and the division must come before the multiplication for the same reason.
n * (n+1) is always even, since one of two consecutive numbers is, so the
halving is exact and loses nothing.
Constraints - `0 ≤ n ≤ 77935` - The bound is chosen so the answer fits in a signed 64-bit integer.
Input
One line containing the integer n.
Output
Print the sum of the cubes of the integers from 1 to n.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.