13
\$\begingroup\$

Recently, I encountered this coding exercise on codility and the idea is

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.

Write a function:

 class Solution { public int[] CyclicRotation(int[] A, int K); }

that, given a zero-indexed array A consisting of N integers and an integer K, returns the array A rotated K times.

For example, given array A = [3, 8, 9, 7, 6] and K = 3

the function should return [9, 7, 6, 3, 8].

Assume that:

N and K are integers within the range [0..100]; each element of array A is an integer within the range [−1,000..1,000].

My approach was if the array has zero or 1 element, the array given is returned else thne for loop is executed. I also added the new array to extract a subset of the array which was meant to be shifted and the first element of Array A is swapped with the last element. Finally, a new list is created with aim to achieve the insert the first element A[0] after being swapped.

public static int[] CyclicRotation(int[] A, int K)
    {
        //Rotate an array to the right by a given number of steps.
        // eg k= 1 A = [3, 8, 9, 7, 6] the result is [6, 3, 8, 9, 7]
        // eg k= 3 A = [3, 8, 9, 7, 6] the result is [9, 7, 6, 3, 8]

        if(A.Length== 0 || A.Length ==1)
        {
            return A;
        }
        int lastElement;
        int[] newArray = new int[A.Length];

        List<int> listOfNumbers = new List<int>();

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

            lastElement = A[A.Length - 1];
            newArray = A.Take(A.Length - 1).ToArray(); 
            listOfNumbers = newArray.ToList<int>();
            listOfNumbers.Insert(0, lastElement);

            A = listOfNumbers.ToArray();
            newArray = A;

        }
        return newArray;
    }

I believe there is room for improvements. Any suggestions would be appreciated.

\$\endgroup\$
  • \$\begingroup\$ Yes there is a lot of room for improvement. That is not efficient. In each loop you are creating two arrays, one list, and insert(0 which are all order N operations. \$\endgroup\$ – paparazzo May 20 '16 at 18:41
  • \$\begingroup\$ You subtract the lengths by one in both lastElement and newArray why not just subtract the length the second you get A? \$\endgroup\$ – 13aal May 20 '16 at 19:49
  • \$\begingroup\$ How would you handle the situation of K > N? \$\endgroup\$ – corsiKa May 21 '16 at 1:39
  • 1
    \$\begingroup\$ Instead of moving the actual data, why dont you just move an index at where to start reading once the array shall be extracted? A lot faster to change one integer than the whole array \$\endgroup\$ – Mattias Åslund May 21 '16 at 7:31
  • \$\begingroup\$ This is a learning project for sure. As @jakub pointed the task is in use since 1986 (or earlier). When you exercise with [1,2,3] all solutions are great. Consider an array of 10B length and you will see that any memory allocation appear to be very costly. \$\endgroup\$ – Alex Kudryashev May 21 '16 at 23:51

10 Answers 10

13
\$\begingroup\$

In place solution

Jon Bentley "Programming Pearls" (1986) has this task as one of problems.

The recommended solution, instead of either:

  • doing K 1-element rotations, using 1 temporary variable, with O(K N) time, which is slow
  • using K-element temporary array, with O(N) time, which is wasteful... but only if there is requirement of doing it in place (and not returning copy, i.e. new N-element array)

is the Aha! solution of using reversals, with the following pseudocode

reverse(A, 0, K-1);
reverse(A, K, A.length()-1);
reverse(A, 0, A.length()-1);

assuming that reverse(A, I, J) operation reverses elements of array A from I-th element to J-th element, inclusive, that is, if $$A=\{a_0,a_1,...,a_i,a_{i+1}...,a_j,a_{j+1}...,a_{N-1}\}$$ then $$\text{reverse}(A, i,j)=\{a_0,a_1,...,a_j,...,a_{i+1},a_i,a_{j+1},...,a_{N-1}\}$$


For example, given array A = [3, 8, 9, 7, 6] and K = 3, the function should return [9, 7, 6, 3, 8].

Steps, corrected for the account of different meaning for K, namely whether it is number of elements to move from left to right ("Programming Pearls"), or from right to left (an example):

  1. [3, 8,| 9, 7, 6] - original array
  2. [8, 3,| 9, 7, 6] - reversed first part
  3. [8, 3,| 6, 7, 9] - also reversed second part
  4. [9, 7, 6,| 3, 8] - the solution

The idea by @forsvarir, namely:

You're currently rotating the array by 1 over and over again. Instead, think about where each element will end up at the end of N rotations. It's end position should be something like (startPos + numberOfRotations) modulus array size.

is another possible algorithm for an in-place rotation in "Programming Pearls". It can be written in an elegant way, but coming up with correct implementation is a bit more tricky. Though it does twice less operations than the reverse based one, each operation is more complex; also it doesn't play well when N is large enough that swap must be used (nowadays probably not a problem).


Return copy solution

If you are returning a copy, you don't need a temporary K-element array. The solution is to create a result by copying appropriate parts.

In pseudocode (and in programming languages where you can do whole (sub)array copy) it would look like this:

Anew = allocate(N)
Anew[0:K-1] = A[N-K-1:N-1]
Anew[K:N-1] = A[0:N-K-1]

Here I assume that K means number of elements from the end to move to beginning, and that A[0:K-1] means array slice (a(1:K) in Fortran).

Note: I have not checked this solution - beware off-by-one errors here.

\$\endgroup\$
  • \$\begingroup\$ I guess this is the goto approach when you want to rotate it in place \$\endgroup\$ – WorldSEnder May 21 '16 at 0:15
  • \$\begingroup\$ [8, 3,| 6, 7, 9] - also reversed second part you are reversing it again as in the last step it is [9,7,6 | 3,8] not [6,7,9 | 3,8] because the original is [3, 8,| 9, 7, 6] so is reversing the 2nd half necessary? \$\endgroup\$ – Simple Fellow Apr 22 at 6:17
6
\$\begingroup\$

Naming

Think about your variable naming. You've used listOfNumbers for your local variable, however your parameter names are A and K. Do they mean anything without looking at the rest of the code?

Break down the problem into methods

The code below looks like it represents rotating the array by 1 place. If so, put it in a method with an appropriate name, then call it. It will make the problem breakdown easier to follow.

lastElement = A[A.Length - 1];
newArray = A.Take(A.Length - 1).ToArray(); 
listOfNumbers = newArray.ToList<int>();
listOfNumbers.Insert(0, lastElement);

A = listOfNumbers.ToArray();
newArray = A;

Think about the algorithm

You're currently rotating the array by 1 over and over again. Instead, think about where each element will end up at the end of N rotations. It's end position should be something like (startPos + numberOfRotations) modulus array size.

\$\endgroup\$
5
\$\begingroup\$

I think there is easier solution without creating additional arrays which only add overhead. All you want to do can be done using your original array and a few int variables. For example:

int len = A.Length; //self explanatory 
int tmp = A[len - 1]; //save last element value
for(int i = len-1;i > 0; i--) //starting from the end to begining
{
   A[i] = A[i - 1]; //assign value of the previous element
}
A[0] = tmp; //now "rotate" last to first.

This is just a fragment of code and further improvements are still possible. For example, you can rotate K times recursively.

\$\endgroup\$
  • \$\begingroup\$ So you think moving one at a time K times is optimal? \$\endgroup\$ – paparazzo May 20 '16 at 18:35
  • \$\begingroup\$ @Paparazzi It's definitely an improvement over the original, which also moves one at a time but creates a new array each iteration. But if your point is there are yet better ways to do things, you're free to offer your own suggestions. \$\endgroup\$ – brian_o May 20 '16 at 18:39
  • \$\begingroup\$ @brian_o The original actually returns the correct answer \$\endgroup\$ – paparazzo May 20 '16 at 18:42
  • \$\begingroup\$ @Paparazzi surely no. This is just first step of improvement. Next steps may include a) optimize the number of steps K % len, b) save first K elements in temp array. Also negative K is a challenge. I'm not the author of the original code and I don't want to do instead of author. \$\endgroup\$ – Alex Kudryashev May 20 '16 at 18:42
  • \$\begingroup\$ @Paparazzi I probably use misleading comment. It should be ...optimize the number of "rotations" K % len and then do all rotations in a single loop. \$\endgroup\$ – Alex Kudryashev May 20 '16 at 18:48
5
\$\begingroup\$

My suggestion is to use the built-in Array.Copy static method to minimize allocation of additional memory:

private static void RotateArrayRight<T>(T[] array, int count)
{
    if (count < 0)
        throw new ArgumentOutOfRangeException("count");
    if (count == 0)
        return;

    // If (count == array.Length) there is nothing to do.
    // So we need the remainder (count % array.Length):
    count %= array.Length;

    // Create a temp array to store the tail of the source array
    T[] tmp = new T[count];

    // Copy tail of the source array to the temp array
    Array.Copy(array, array.Length - count, tmp, 0, count);

    // Shift elements right in the source array
    Array.Copy(array, 0, array, count, array.Length - count);

    // Copy saved tail to the head of the source array
    Array.Copy(tmp, array, count);
}

Usage:

int[] a = { 1, 2, 3, 4, 5, 6, 7 };
RotateArrayRight(a, 2);
// Now: a = { 6, 7, 1, 2, 3, 4, 5 }

The same approach with immutable source array:

private static T[] RotateArrayRight<T>(T[] array, int count)
{
    if (count < 0)
        throw new ArgumentOutOfRangeException("count");

    // If (count == array.Length) there is nothing to do.
    // So we need the remainder (count % array.Length):
    count %= array.Length;

    // Create a temp array to store the result
    T[] tmp = new T[array.Length];

    // Copy the last {count} elements of the source array to the head of the temp array
    Array.Copy(array, array.Length - count, tmp, 0, count);
    // Copy the rest elements
    Array.Copy(array, 0, tmp, count, array.Length - count);

    return tmp;
}

Usage:

int[] a = { 1, 2, 3, 4, 5, 6, 7 };
a = RotateArrayRight(a, 2);
// Now: a = { 6, 7, 1, 2, 3, 4, 5 }
\$\endgroup\$
  • \$\begingroup\$ What happens when you rotate a 4 element array 5 times? :-) \$\endgroup\$ – brian_o May 20 '16 at 19:41
  • 1
    \$\begingroup\$ @brian_o, I've added a fix: count %= array.Length;. Thanks. \$\endgroup\$ – Dmitry May 20 '16 at 19:44
4
\$\begingroup\$

You have an interface problem... caller passes an array and receives an array as return value. Is the return value meant to be a handle to the same array or a copy? Right now the behavior is inconsistent and depends on the size of the array argument.

    static void DumpArray(int[] array)
    {
        foreach (var element in array)
        {
            Console.Write(element);
            Console.Write(" ");
        }
        Console.WriteLine();
    }

    static void Main(string[] args)
    {
        {
            int[] untouchable = { 1, 2, 3 };
            DumpArray(untouchable);
            var rotated = CyclicRotation(untouchable, 2); // won't change "untouchable"
            rotated[0] = 9;
            DumpArray(untouchable); // good, still untouched
            DumpArray(rotated);
        }
        {
            int[] untouchable = { 1 };
            DumpArray(untouchable);
            var rotated = CyclicRotation(untouchable, 2); // won't change "untouchable"?
            rotated[0] = 9;
            DumpArray(untouchable);  // oh no! mutated!
            DumpArray(rotated);
        }
    }

    public static int[] CyclicRotation(int[] A, int K)
    {
        ...
    }

To make it consistent (and I think more intuitive), you can change the guard condition to if (A.Length == 0 || A.Length == 1) return (int[])A.Clone();. Better yet, rework your algorithm a bit and you won't need a special case.

Regardless, you should document the expected behavior and make sure your implementation actually follows through.

\$\endgroup\$
  • \$\begingroup\$ I am passing a copy of the array as an input- passing by value rather than reference. Hence, the newArray was returned rather than the original A \$\endgroup\$ – Siobhan May 21 '16 at 22:11
  • \$\begingroup\$ @TolaniJaiye-Tikolo That may have been your intention, but what I'm saying is that in the case of a 1 element array, your original code does not return a copy of the array but rather the original array. In your original code, for 2+ element arrays, you indeed return a copy. \$\endgroup\$ – brian_o May 22 '16 at 4:15
3
\$\begingroup\$

You could do the following:

var sample = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
var rotatedSample = Rotate(sample, 3);

protected static IEnumerable<int> Rotate(int[] source, int rotation)
{
     var temporary = source.Take(rotation);
     return source.SkipWhile(index => index <= rotation).Concat(temporary);
}

The benefit of this approach is simplicity. It will take based on the rotation, causing you to hold the original position's of your contents, but it will also shift the entire contents accordingly. Then you simply append the temporary to the end of the source, causing you to shift the entire array.

The performance may not be quite as quick as some other approaches, but the simplicity of syntax I feel is a valid trade off.

\$\endgroup\$
2
\$\begingroup\$

As others have mentioned, your solution is more involved (and slower) than necessary.

I would do this using an Int pointer that is an offset (mod "ArraySize") into the array, rather than actually moving elements within an array.

When you want to rotate the array, k steps to the right, then simply use k mod ArraySize.

When you need to access element N (0 for example) of array A, you read A[(0 + Offset) mod ArraySize].

The code below assumes that like the example in the original post, the "exercise" requires that the function has to return the original array (A), rotated, as a "new Array". If this is not really necessary, then the code below can be simplified even further.

I have also kept the same variable names you used in you example (A, k), because I assume those are the variable names given to you in the "exercise". Otherwise, consider making these names more descriptive.

Lastly, in your code, you have made a special case for when the size of the array (A) is "0 or 1". In the code below, these are handled naturally by the code and no special case treatment is necessary.

public static int[] RotateR(int[] A, int k)
    {
    //  Rotate an array to the right by a given number of steps.
    //  eg k= 0 A = [3, 8, 9, 7, 6] the result is newArray = [3, 8, 9, 7, 6]
    //  eg k= 1 A = [3, 8, 9, 7, 6] the result is newArray = [6, 3, 8, 9, 7]
    //  eg k= 3 A = [3, 8, 9, 7, 6] the result is newArray = [9, 7, 6, 3, 8]

    //  int iOffset;
        int iArraySize=A.Length;
        int[] newArray = new int[iArraySize];

        for (int i = 0; i < iArraySize; i++)
        {
    //      iOffset=(k+i) % iArraySize;
    //      newArray[i] = A[iOffset];
            newArray[i] = A[(k+i) % iArraySize];
        }
        return newArray;
    }
\$\endgroup\$
1
\$\begingroup\$

Inefficient
In a loop you create 2 array, 1 list, and 1 insert at 0.
All of those are O(n) operations
You should not have any O(n) operations in the loop

public static int[] CyclicRotation(int[] A, int K)
{
    //Rotate an array to the right by a given number of steps.
    // eg k= 1 A = [3, 8, 9, 7, 6] the result is [6, 3, 8, 9, 7]
    // eg k= 3 A = [3, 8, 9, 7, 6] the result is [9, 7, 6, 3, 8]

    if(K > arr.Lengh || k < 0) throw new Excetion();

    if(A.Length <=1 || K == 0)
    {
        return A.Clone();
    }

    // get a copy of the last k
    int[] last = new int[K];
    for (int i = 0; i < k; i++)
    {
        last[i] = A[a.A.Length - k + i];
    }

    // shift k 
    int[] newArray = new int[A.Length];
    for (int i = A.Length - 1; i >= k; i--)
    {
        newArray[i] = A[i - k];
    }

    // copy the last 3 back
    for (int i = 0; i < k; i++)
    {
        newArray[i] = last[i];
    }

    return newArray;
}
\$\endgroup\$
1
\$\begingroup\$

This is an excellent opportunity to use a LinkedList<int>.

To generalize the solution a bit, we can pass a boolean to a Rotate() method that determines the direction to rotate.

using System.Collections.Generic;
using System.Linq;

public class NumberArrayRotater
{
    public int[] Rotate(int[] numbers, int cycles, bool goRight)
    {
        var linkedList = new LinkedList<int>(numbers);
        if (goRight)
        {
            for (var i = 0; i < cycles; ++i)
            {
                var node = linkedList.Last;
                linkedList.RemoveLast();
                linkedList.AddFirst(node);
            }

            return linkedList.ToArray();
        }

        for (var i = 0; i < cycles; ++i)
        {
            var node = linkedList.First;
            linkedList.RemoveFirst();
            linkedList.AddLast(node);
        }

        return linkedList.ToArray();
    }
}

Also note that we could easily accept an IEnumerable<int> instead of an array.

\$\endgroup\$
  • \$\begingroup\$ I have further generalized this and some other transformations that may be done to enumerables here. \$\endgroup\$ – xofz Jul 3 '16 at 6:18
0
\$\begingroup\$

There are two ways to do this - by the Programming Pearls swap trick, and by recursive rotation. The swap code is simpler to write and easier to prove, but the rotation code can be faster. Here's a worked example of each algorithm.

#include <stdio.h> 
#include <stdlib.h> 

// Rotate a subset of a array 

//           0 1 2 3 4 5 6 7 8 9 
// eg rotate A B C D E F G H I J, 2, 3, 8 
//               \_/ \_______/ 

// =>        A B E F G H I C D J 
//               \_______/ \_/ 


void reverse(int *A, int low, int high) 
{ 
  while (low < high) { 
    register int temp = A[low]; 
    A[low++] = A[high]; 
    A[high--] = temp; 
  } 
} 

void rotate_by_reversals(int *A, int first_index, int rot_index, int last_index) 
{ 
  //               f r         l 
  //           0 1 2 3 4 5 6 7 8 9 
  // eg rotate A B C D E F G H I J, 2, 3, 8 
  //               \_/ \_______/ 
  // =>        A B E F G H I C D J, 2, 3, 8 
  //               \_______/ \_/ 



  if (first_index == rot_index || rot_index+1 == last_index) return; 
  reverse(A, first_index, rot_index); 
  //               f r         l 
  //           A B C D E F G H I J 
  //               \_/ 
  // =>        A B D C E F G H I J 

  reverse(A, rot_index+1, last_index); 
  //               f r         l 
  //           A B D C E F G H I J 
  //                   \_______/ 
  // =>        A B D C I H G F E J 

  reverse(A, first_index, last_index); 
  //               f r         l 
  //           0 1 2 3 4 5 6 7 8 9 
  //           A B D C I H G F E J 
  //               \___________/ 

  // =>        A B E F G H I C D J 
  //               \___________/ 

} 

void swap_blocks(int *A, int left, int right, int len) 
{ 
  // preserve order 
  while (len-- > 0) { 
    register int temp = A[left]; 
    A[left++] = A[right]; 
    A[right++] = temp; 
  } 
} 

void rotate_by_blocks(int *A, int first_index, int rot_index, int last_index) 
{ 
  int len; 
  while (first_index != last_index) { // while loop replaces recursion
  if (rot_index-first_index+1 < last_index-rot_index) { 

    len = rot_index-first_index+1; 

    //               f r         l 
    //           0 1 2 3 4 5 6 7 8 9 
    // eg rotate A B C D E F G H I J, 2, 3, 8 
    //               \_/ \_______/ 

    // =>        A B E F G H I C D J 
    //               \_______/ \_/ 


    swap_blocks(A, first_index, rot_index+1, len); 
    //               f r         l 
    //           0 1 2 3 4 5 6 7 8 9 
    //           A B C D E F G H I J 
    //               \_/ \_/ 
    // =>        A B E F C D G H I J 
    //               \_/ \_/ 

    // rotate_by_blocks(A, rot_index+1, rot_index+len, last_index); 
                           first_index = rot_index+1; 
                                        rot_index += len; 
    //               f r         l 
    //           A B E F C D G H I J 
    //                   \_/ \___/ 
    // =>        A B E F G H I C D J 
    //                   \___/ \_/ 

  } else { 
    len = last_index-rot_index; 
    //               f       r   l 
    //           0 1 2 3 4 5 6 7 8 9 
    // eg rotate A B C D E F G H I J, 2, 6, 8 
    //               \_______/ \_/ 
    // =>        A B H I C D E F G J 
    //               \_/ \_______/ 


    swap_blocks(A, rot_index-len+1, last_index-len+1, len); // or rot_index, last_index, -len ??? 
    //               f       r   l 
    //           0 1 2 3 4 5 6 7 8 9 
    //           A B C D E F G H I J 
    //                     \_/ \_/ 
    // =>        A B C D E H I F G J 

    // rotate_by_blocks(A, first_index, rot_index-len, rot_index); 
                                                       last_index = rot_index; 
                                        rot_index -= len; 
    //               f       r   l 
    //           A B C D E H I F G J 
    //               \___/ \_/ 
    // =>        A B H I C D E F G J 
    //               \_/ \___/ 
  } 
  } 
} 

int main(int argc, char **argv) { 
  int fred[10], i; 

  for (i = 0; i < 10; i++) fred[i] = i+'A'; 
  fprintf(stdout, "rotate_by_reversals(ABCDEFGHIJ, 2, 3, 8) => "); 
  rotate_by_reversals(fred, 2, 3, 8); 
  for (i = 0; i < 10; i++) putchar(fred[i]); putchar('\n'); 

  for (i = 0; i < 10; i++) fred[i] = i+'A'; 
  fprintf(stdout, "rotate_by_blocks(ABCDEFGHIJ, 2, 3, 8) => "); 
  rotate_by_blocks(fred, 2, 3, 8); 
  for (i = 0; i < 10; i++) putchar(fred[i]); putchar('\n'); 

  exit(0); 
  return(1); 
}
\$\endgroup\$
  • \$\begingroup\$ Hi. Welcome to Code Review! It is more customary to write answers in the same language as the question. Also, you don't explain why either of these would be better than the original solution or other solutions. I also find the way that you comment out a recursive solution and add an iterative solution a bit confusing. It's not clear what code is shared between the two versions and what is specific to the iterative version. \$\endgroup\$ – mdfst13 May 21 '16 at 0:39

protected by Community Nov 7 '16 at 13:05

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.