# 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(n^{2}) 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. } }

**Note:**See TracWiki for help on using the wiki.