Algo Puzzle #1

I am a jovial fan of algorithmic puzzles so I decided to create some myself and put them on my blog. I will post them one at a time.

You will find the first puzzle down below and the solution will be posted in the comments section over the weekend. The puzzles will gradually get more difficult ;)

Algo Puzzle #1

Write an algorithm that sums a set where each number is from 1 to n in O(1) time. More specifically find an algorithm that computes it with only 3 operations regardless of the set's size.

Swapping elements in an array without a temporary variable

The common idiom to swap two elements in an array is to use a temporary variable that is consequently pushed on the stack, which looks like the following:

int[] elements = {1,2,3,4,5,6,7,8,9,10}
int tmp = elements[0];
elements[0] = elements[9];
elements[9] = tmp;


In that example I was swapping the first and last elements. However this is not the most optimized way as the elements can be swapped without that temporary variable being created.

In true blue peter style, here's one I created earlier:

elements[0] = elements[0]^[elements[9];
elements[9] = elements[0]^[elements[9];
elements[0] = elements[0]^[elements[9];

It works in the same way that algebra works, where equality can be changed w.r.t the variable.

a = b - c
b = a + c
c = b - a

The bitwise operators only work on integers and not all real numbers (more speficially, floating point numbers) so the arithmetic operators must be used instead to swap real numbers in an array:

float[] data = {1.1f, 2.234f, 4.5454f, 1.110f, 9.999f, 3.1562f};
data[0] = data[0] - data[5];
data[0] = data[5] + data[0];
data[5] = data[0] - data[5];

Using these algorithms will provide micro-optimization but at the expense of clarity.