Editorial for Lyndon's Golf Contest 1 P2 - A Cube Problem


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Dingledooper

35 bytes

A blind, brute-force implementation of this problem might involve iterating over every integer from 1 to n, adding its cube to a running sum, and finally printing the answer at the end. This method is slow, but it's also rather long. It turns out that an explicit formula exists for this problem that allows us to solve it in \mathcal{O}(1). More specifically, it can be shown that the sum of the first n cubes is equivalent to the sum of the first n positive integers, squared, which can simply be written as \left(\frac{n(n+1)}{2}\right)^2. The proof is left as an exercise to the reader.

Alternatively, you can search the OEIS and find the sequence to be A000537. With that, we can achieve a 37-byte solution by simply applying the formula:

n=int(input())
print((n*(n+1)//2)**2)

To obtain 35 bytes, we can expand n(n+1) to n^2+n, and switch the division operator (//) for a bitwise-right shift (>>) to lower the precedence:

n=int(input())
print((n*n+n>>1)**2)

34 bytes

Recall that the unary operator ~ takes the bitwise NOT of a given number. Due to two's complement, ~n happens to be equivalent to -(n+1). Using this observation, we may find that our previous 37-byte solution could have also been reduced to 35:

n=int(input())
print((n*-~n//2)**2)

The final byte save lies in the fact that the square of a negative number is always positive, and thus we can deduce that the - in our formula can be omitted to obtain our final solution of 34 bytes:

n=int(input())
print((n*~n//2)**2)

Comments

There are no comments at the moment.