Luckily the problems were solved in the comments, so I will just explain how the solutions work and show some additional solutions to the problems. This post will only cover solutions for the in-place rotation problem, as the unified post was becoming too long.

##### Demian’s solution

Demian found a very interesting linear time solution to the in place rotation problem. This is a cleaned up version that avoids carrying temporary values in the inner loop:

import fractions def swap(a, i, j): a[i], a[j] = a[j], a[i] def rotate_right_in_place(a, k): n = len(a) gcd = fractions.gcd(n, k) for i in range(gcd): for j in range(1, n // gcd): swap(a, i, (i + j * k) % n)

This code has two nested loops. The outer one moves between “cycles” (to be defined afterwards) and the inner one rotates the elements of one cycle. When all cycles are rotated, the array rotation is complete.

Let’s start by analyzing the rotation of a single cycle: a cycle is a sequence of elements in the array *a* that can be obtained by taking *a* as circular and advancing steps of length *k* until reaching the start point. To get the cycle length *c*, we can assume that the cycle starts at element *i* and see how many steps of length *k* we need to make to reach the position *i* again:

(*i* + *c* * *k*) % *n* = *i*

*i* % *n* + (*c* * *k*) % *n* = *i* % *n*

(*c* * *k*) % *n* = 0

So we are looking for the smallest multiple of *k* that is also a multiple of *n*, the least common multiple:

*c* * *k* = lcm(*n*, *k*)

Expressing the least common multiple in terms of the greatest common divisor and simplifying:

*c* * *k* = *n* * *k* / gcd(*n*, *k*)

*c* = *n* / gcd(*n*, *k*)

As we are in a single cycle of length *c*, the elements can be rotated with just *c* – 1 swaps:

*a*[*i*] ↔ *a*[(*i* + *k*) % *n*]

*a*[*i*] ↔ *a*[(*i* + 2 *k*) % *n*]

…

*a*[*i*] ↔ *a*[(*i* – *k*) % *n*]

After each swap, the array position at the right side has the correct value and the array position at the left side has the element to be positioned in the next swap. As each of the *c* – 1 swaps has a different right side, at least *c* – 1 elements of the cycle must be in their final positions after the swaps. As we cannot have a single misplaced element in a cycle, all the elements must in their places after the swaps.

We can see by a simple counting argument that there are *n* / (*n* / gcd(*n*, *k*)) = gcd(*n*, *k*) different cycles. As all the positions in a cycle have the same residue modulo gcd(*n*, *k*), we can move through all the cycles by selecting 0, 1, 2, …, gcd(*n*, *k*) – 1 as cycle starting points.

##### My solution

My solution is quite uglier:

def rotate_right_in_place(a, k, offset=0, n=None): n = len(a) if n is None else n k %= n if k == 0: return if k * 2 > n: s = n % k for i in xrange(0, n - 2 * s, s): for j in xrange(s): swap(a, i + j + offset, i + j + s + offset) if n > i + 2 * s: rotate_right_in_place(a, n - (i + 2 * s), offset + i + s, n - (i + s)) else: s = k for i in xrange(n - s, s - 1, -s): for j in xrange(s): swap(a, i + j + offset, i + j - s + offset) if i > s: rotate_right_in_place(a, s, offset, i)

This solution is a maze of special cases and index arithmetic, but the internal workings aren’t very interesting: it just swaps blocks whose size and position is selected to avoid conflicts. As the sequence length is not a multiple of the block size, it recurs to solve this remaining subproblems as rotations of a smaller segment.

##### Reversing solution

I found this solution searching in some interview problems site:

def rotate_right_in_place(a, k): n = len(a) for i in xrange(n // 2): swap(a, i, (n - 1) - i) for i in xrange(k // 2): swap(a, i, (k - 1) - i) for i in xrange((n - k) // 2): swap(a, k + i, (n - 1) - i)

It’s quite elegant and certainly simpler than the previous solutions.

##### Comparison

Let’s compare the number of swaps required by the different solutions when rotating an array of 97 elements by 43 positions:

Number of swaps (len(a) = 97, k = 43) rrip_copied: 96 rrip_demian: 0 rrip_demian2: 96 rrip_mariano: 96

In this case all the solutions match (*rrip_demian* doesn’t use swaps, but it does the same number of equivalent operations) and, through further testing, we see that none of the solutions exceeds *n* swaps to rotate a *n* element array. In some cases the “reversing solution” requires a few more swaps than the other ones.

The reversing solution is pure win!

Also, it should be quite more cache-friendly than the solution I found (yeah yeah, premature optimizaton… but it WAS an optimization problem after all!).

Your solution seems like a quite hacky way of solving the problem recursively =P (it took me quite some time to realize what it was suposed to do hehe)

Also, how weird it is to read one’s own name in an blog post :S

Yes, it’s quite hacky. I started trying to rotate the array swapping blocks, but this doesn’t work directly because the required block sizes aren’t divisors of the array size.

Then I saw that I could rotate the remaining sections recursively, without losing the linear time complexity, and I stopped thinking. Maybe there is a cleaner version of my algorithm, but life is too short to spend it searching for cleaner versions of all possible in place array rotation algorithms 😛

The reversing solution is also in a small book about algorithms called “Programming Pearls”: http://www.cs.bell-labs.com/cm/cs/pearls/

Thanks for the info! It’s a great book, but for some reason the only algorithm from it I remember is the phone number sorting one. :-S

Sorry I forgot to paste the relevant link: http://www.cs.bell-labs.com/cm/cs/pearls/s02b.pdf

[…] the solutions that were given in the comments of the “two coding problems” post. As the first problem was already discussed, this post will only be about the second […]