Two coding problems – Solutions Part I

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.

Advertisement