A Constant Solution to Code-Fights Apple Boxes Problem

The Apple Boxes Problem

The problem can be simply put:

Input:

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

The Naive Solution

We can loop through 1 to , 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 .

Constant Solution

First, assume is even, so that we can perfectly pair up terms in and . Observe that each pair is in the form of . This can be transformed to . When we add all pairs, it becomes a simple series: . For example, for :

Thus, we can return for arbitrary even .

What about odd ? We can adjust the pairing a little bit, and easily find that now we have .

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++