A Constant Solution to Code-Fights Apple Boxes Problem

The Apple Boxes Problem

The problem can be simply put:

Input: $k$

Output: let $r$ be the sum of the square of each even integer no larger than $k$, and $y$ be that of the odd. Return $r - y$.

The Naive Solution

We can loop through 1 to $k$, alternating between adding and subtracting.

val = 0
for i in [1..k]
if i % 2 == 0
val += i * i
else
val -= i * i

return val


There could be various optimizations, but nevertheless, the algorithm is linear with regards to $k$.

Constant Solution

First, assume $k$ is even, so that we can perfectly pair up terms in $r$ and $y$. Observe that each pair is in the form of $x^2 - (x - 1)^2$. This can be transformed to $(x + x - 1)\cdot(x - x + 1) = (x - 1) + x$. When we add all pairs, it becomes a simple series: $1 + 2 + 3 + ... + k$. For example, for $k = 6$:

Thus, we can return $\dfrac{k(1 + k)}{2}$ for arbitrary even $k$.

What about odd $k$? We can adjust the pairing a little bit, and easily find that now we have $-\dfrac{k(1 + k)}{2}$.

C++ Source Code

int appleBoxes(int k) {
int sum =  (1 + k) * k / 2
return (k % 2 == 1) ? -sum : sum;
}


COMSCI
computer science algorithm codefights C++