Spacing elements in a circular array

Question

This is an interesting problem I've come across that I feel should have an elegant, provable solution but I haven't quite been able to get it. I've defined it as:

Define a function that takes as input an array of N elements and a positive integer R, and returns a circular array (or an array that you treat as circular) where no two identical elements are less than R apart, or a null if no such ordering is possible.

So f([a,b,d,c,a,d,k,a,d], 3) might return [a,b,d,a,k,d,a,c,d], but f([a,b,d,c,a,d,k,a,d,a,a], 3) would return null. I define two elements as being R apart if they have R-1 elements between them, so in the array [x,a,b,y], x and y are 3 apart on one side and 0 apart on the other.

I feel like this would be a great interview question as well.

Answer 1

1. Split the array into groups of identical elements (with sorting or using a hashtable).
2. Find the largest group. If its size is greater than floor(N/R), return null.
3. If size of the largest group equals exactly N/R, partition (partially sort) the list of groups, so that all the groups of size N/R come first in the following step.
4. For each group, put its elements to the result array (circular buffer), incrementing index by R, while it is possible. If R and N are not co-prime, sometimes - after N/GCD(N,R) increments - index will point to already used element. In such cases increment index by R+1 instead of R and continue.