# Remembering How to Rotate an Array

For no reason that I can remember, I was recently reminded of a solution to a homework problem way back from my first semester in college that I thought was creative. Having not had anything to say here for four months, I thought it would be fun to dig up the code and take a look.

The challenge was to rotate a vector in place using constant extra memory and less than O(n2) moves. There was very little additional information. I remember scratching my head for a while and then coming up with this crazy scheme involving the greatest common divisor which I drew out in great detail with boxes and arrows explaining how everything would move. I was disgusted that I couldn't arrive at a way to remove the gcd function entirely.

Now that I look, I see it is an early problem in book Programming Pearls. Their solutions can be found here. Algorithm 3 is the closest to mine, and they indeed don't need to calculate the gcd ahead of time.

Oh, and I was sloppy with whitespace and some other details back then.

```/* Euclid's algorithm for calculating the greatest common divisor of two numbers.
Taken from page 58 of "Data Structures & Algorithm Analysis in C++ Second Edition" by Mark Allen Weiss. */
int gcd(int a, int b)
{
while (b)
{
int r = a % b;
a = b;
b = r;
}

return a;
}

/* Rotates a vector i steps, using minimal moves.
This requires an "extra" calculation of the greatest common divisor of i and v.size(), but this algorithm
still wins out over rotating v one element at a time i times, because this is O(n) while the latter method is O(n^2) */
template<class T> void rotate(vector<T> &v, int i)
{
int size = v.size();
int factor = gcd(size, i);
i %= size;

int p;

for (p = 0; p < factor; p++)
{
int n;
T temp = v[p];  // Pull out one element so we can shift everything forward.
for (n = (p + i) % size; n != p; n = (n + i) % size)    // Until we get back to where we start, shift each element forward.
v[(n - i + size) % size] = v[n];

v[(p - i + size) % size] = temp;        // Put back original element.
}
}
```