# 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

eveninteger no larger than , and be that of theodd. 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;
}
```

Power Snail COMSCI

computer science algorithm codefights C++