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 regard 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$:

$$ \begin{align*} r &= 2^2 + 4^2 + 6^2 \\ y &= 1^2 + 3^2 + 5^2 \\ r - y &= (2^2 + 4^2 + 6^2) - (1^2 + 3^2 + 5^2) \\ &= (2^2 - 1^2) + (4^2 - 2^2) + (6^2 - 5^2) \\ &= 1 + 2 + 3 + 4 + 5 + 6 \\ &= \dfrac{6(1 + 6)}{2} \\ &= 21 \end{align*} $$

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

What about odd $k$? We can adjust the pairing a 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;
}