Editorial for Lyndon's Golf Contest 1 P2 - A Cube Problem
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
35 bytes
A blind, brute-force implementation of this problem might involve iterating over every integer from to , 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 . More specifically, it can be shown that the sum of the first cubes is equivalent to the sum of the first positive integers, squared, which can simply be written as . 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 -byte solution by simply applying the formula:
n=int(input())
print((n*(n+1)//2)**2)
To obtain bytes, we can expand to , 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 -byte solution could have also been reduced to :
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 bytes:
n=int(input())
print((n*~n//2)**2)
Comments