Codility CyclicRotation in-place implementation

Question

I can't wrap my head around my solution for the problem:

A zero-indexed array A consisting of N integers is given. Rotation of the array means that each element is shifted right by one index, and the last element of the array is also moved to the first place.

For example, the rotation of array A = [3, 8, 9, 7, 6] is [6, 3, 8, 9, 7]. The goal is to rotate array A K times; that is, each element of A will be shifted to the right by K indexes.

I wanted to create solution without creating new array, but just modifying the one in place. It works... most of the time. Example tests pass, and other also pass, but some, for which Codility doesn't show the input, fail.

public int[] solution(int[] A, int K) {
    for (var i = 0; i < A.Length - 1; i++) {
        var destIndex = (i * K + K) % A.Length;
        var destValue = A[destIndex];
        A[destIndex] = A[0];
        A[0] = destValue;
    }
    return A;
}

I've skipped the code related to the fact that you don't need to rotate whole array few times (ie. rotating by A.Length % K is enough).

What's wrong with my implementation? Am I missing some corner case?

Answer 1

The algorithm for this should be very simple, like:

aux <- array[array.Length - 1]

for index = 0, array.Length - 2 do
    array[index + 1] <- array[index]
    array[0] <- aux
endfor

Note, that in the special cases when array.Length <= 1, you do not need anything to achieve the rotation. If you want to achieve K rotations without an array, you can call this K times.

You will need to be tricky to achieve an optimal algorithm. Here I will take the following approach. An array's given element can have three different possible states. I explain it through the example. If I put the K'th element into a variable called aux and place the 0'th element in its place, then we have the following three states:

• at element 0 the original element was already moved to another place, but the final element did not arrive yet. This is the moved state
• at element K the original element was already moved and the final element already arrived there. This is the arrived state
• at element 2 * K we did nothing so far, so there we have the original state

So, if we can mark somehow the elements, then the algorithm would look like this:

arrivedCount <- 0 //the number of arrived elements is counted in order to make sure we know when we need to search for an element with an original state

    index <- 0
    N <- array.Length
    aux <- array[index]
    mark(array[index], moved)
    index <- (index + K) mod N
    while arrivedCount < N do
        state <- array[index]
        if (state = moved) then
            array[index] <- aux
            arrivedCount <- arrivedCount + 1
            mark(array[index], arrived)
            if arrivedCount < N then
                while (state(array[index]) <> original) do
                    index <- (index + 1) mod N
                endwhile
                aux <- array[index]
                mark(array[index], moved)
                index <- (index + K) mod N
            endif
        else //it is original
            aux2 <- array[index]
            array[index] <- aux
            aux <- aux2
            arrivedCount <- arrivedCount + 1
            mark(array[index], arrived)
            index <- (index + K) mod N
        endif
    endwhile

Now, how could we use this in practice? Let's consider the example when your array only has positive numbers as value. You mark all elements at start by assigning them their negative value (-5 instead of 5, for example). Whenever a state is modified to move, it will have a value of 0 and whenever it is arrived, you will have the positive number. It is up to you to define how you can mark such elements and you will need to do this in conformity with your task. If you are unable to mark the elements for any reason, then you will need to create an auxiliary array in order to solve this.

EDIT

Do not be afraid of the while, it should not search for too many steps because of the modulo classes. An implementation in Javascript:

var array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
var arrivedCount = 0;
var index = 0;
var N = array.length;
var K = 3;
for (var i = 0; i < array.length; i++) array[i] = -array[i];
var aux, aux2, state;
aux = array[index];
array[index] = 0;
index = (index + K) % N;
var step = 0
while ((arrivedCount < N) && (++step < 1000)) {
    if (array[index] === 0) {
        array[index] = -aux;
        arrivedCount++;
        if (arrivedCount < N) {
            while (array[index] >= 0) index = (index + 1) % N;
            aux = array[index];
            array[index] = 0;
            index = (index + K) % N;
        }
    } else {
        aux2 = array[index];
        array[index] = -aux;
        aux = aux2;
        arrivedCount++;
        index = (index + K) % N
    }
}

Change the definition of array and K according to your will.

Answer 2

I've finally managed to find out what's wrong with my solution thanks to @dvaergiller who posted the question with a similar to mine approach: Fastest algorithm for circle shift N sized array for M position

This answer made me realize my solution is failing every time the greatest common divisor of A.Length and K is not 1. @IsaacTurner solution is much easier to understand, and also shows there's no need to constantly switch places of elements, but now I see I can correct my solution.

I basically should not go through all elements in the array to find correct place for every one of them, because if the greatest common divisor is not 1 I'll start switching elements again. Instead it must be stopped as soon as full cycle is made and restarted to start switching based on next position.

Here's corrected version of my solution:

int gcd(int a, int b) => b == 0 ? a : gcd(b, a % b);

public int[] solution(int[] A, int K)
{
    for (var i = 0; i < gcd(A.Length, K); i++)
    {
        for (var j = i; j < A.Length - 1; j++)
        {
            var destIndex = ((j-i) * K + K + i) % A.Length;
            if (destIndex == i) break;
            var destValue = A[destIndex];
            A[destIndex] = A[i];
            A[i] = destValue;
        }
    }

    return A;
}

Answer 3

You can try this, I got a 100%:

   public int[] solution(int[] A, int K) {

        if (A.length == 0) {
            return A;
        }

        for (int i=0;i<K;i++) {

            int[] aux = new int[A.length];
            aux[0] = A[A.length-1];
            System.arraycopy(A, 0, aux, 1, A.length - 1);
            A = aux;
        }

        return A;
    }

Answer 4

The time complexity of this would be really less :)
I tried a different approach I believe, without loops:

https://app.codility.com/demo/results/trainingE33ZRF-KGU/

public static int[] rotate(int[] A, int K){
    if ( K > A.length && A.length > 0)
        K = K % A.length;
    if (K == A.length || K == 0 || A.length == 0){
        return A;
    }
    int[] second = Arrays.copyOfRange(A, 0, A.length - (K));
    int[] first = Arrays.copyOfRange(A, A.length - (K), A.length );
    int[] both = Arrays.copyOf(first, first.length + second.length);
    System.arraycopy(second, 0, both, first.length, second.length);
    return both;
}

Answer 5

Each element is shifted right by one index, and the last element of the array is also moved to the first place.

public int[] solution(int[] A, int K) {
 if (K > 0 && A.length > 0) {
  K = K % A.length;
  int[] B = new int[A.length];
  for (int i = 0; i < A.length; i++) {
   if ((i + K) > (A.length - 1)) {
    B[i + K - A.length] = A[i];
   } else {
    B[i + K] = A[i];
   }
  }
  return B;
 } else {
  return A;
 }
}