Hacker Rank: Array left rotation

Question

This code is to solve the Hacker Rank problem array left rotation.

A left rotation operation on an array of size n shifts each of the array's elements 1 unit to the left. For example, if 2 left rotations are performed on array [1,2,3,4,5], then the array would become [3,4,5,1,2].

Given an array of n integers and a number, d, perform d left rotations on the array. Then print the updated array as a single line of space-separated integers.

public static int[] rotLeft(int[] a, int d)
    {
        for (int intI = 0; intI < d; intI++)
        {
            int temp = 0;
            temp = a[0];
            for (int intK = 0; intK < a.Length; intK++)
            {
                a[a.Length - (a.Length - intK)] = a.Length - 1 == intK ? temp : a[a.Length - (a.Length - (intK + 1))];
            }
        }
        return a;
    }
    static void Main(string[] args)
    {
        string[] nd = Console.ReadLine().Split(' ');
        int n = Convert.ToInt32(nd[0]);
        int d = Convert.ToInt32(nd[1]);
        int[] a = Array.ConvertAll(Console.ReadLine().Split(' '), aTemp => Convert.ToInt32(aTemp));
        int[] result = rotLeft(a, d);
        Console.WriteLine(string.Join(" ", result));
    }

This program works fine, but it takes too long with some examples. How can I improve it?

Answer 1

About naming:

intI and intK: don't include the type in the variable name, it is obvious from the context and intellisense and as a loop index a plain i and k are more understandable.

---

A first simple optimization is that you can avoid the check if intK has reached the end:

a.Length - 1 == intK ?

Instead you can just iterate up to a.Length - 1 and then append temp at the end:

public static int[] rotLeft(int[] a, int d)
{
  for (int intI = 0; intI < d; intI++)
  {
    int temp = a[0];

    for (int intK = 0; intK < a.Length - 1; intK++)
    {
      a[a.Length - (a.Length - intK)] = a[a.Length - (a.Length - (intK + 1))];
    }

    a[a.Length - 1] = temp;
  }

  return a;
}

---

Next step is to consider the math:

a.Length - (a.Length - intK) = a.Length - a.Length + intK = intK

and in the same way:

a.Length - (a.Length - (intK + 1)) = intK + 1

So you could write:

public static int[] rotLeft(int[] a, int d)
{
  for (int intI = 0; intI < d; intI++)
  {
    int temp = a[0];

    for (int intK = 0; intK < a.Length - 1; intK++)
    {
      a[intK] = a[intK + 1];
    }

    a[a.Length - 1] = temp;
  }

  return a;
}

---

But the real performance problem is that you move each entry in the array d number of times. You can move each entry just once by moving it d places. A simple way to do that could be:

public static int[] rotLeft(int[] a, int d)
{
  int[] temp = new int[d];

  for (int i = 0; i < d; i++)
    temp[i] = a[i];

  for (int i = d; i < a.Length; i++)
  {
    a[i - d] = a[i];
  }

  for (int i = 0; i < d; i++)
    a[a.Length - d + i] = temp[i];

  return a;
}

---

Another issue is that you operate on the input array a directly and return it as a return value. In this way both the return value and a contains the shifted values. In a challenge like this it may not be important, but I think I would return a new array with the shifted data leaving a unchanged - in "real world":

public static int[] rotLeft(int[] a, int d)
{
  int[] result = new int[a.Length];

  for (int i = d; i < a.Length; i++)
  {
    result[i - d] = a[i];
  }

  for (int j = 0; j < d; j++)
  {
    result[a.Length - d + j] = a[j];
  }

  return result;
}

If you want to operate on a directly intentionally it would be more consistent returning void to signal that you're operating on the input directly.

Answer 2

I guess your code is slow because of the two loops and its O(n^2) complexity. You can actually solve it with only one loop by rotating the index with % (modulo). This would even allow you to rotate the array in both directions;

public static IEnumerable<T> Shift<T>(this T[] source, int count)
{
    for (int i = 0; i < source.Length; i++)
    {
        var j =
            count > 0
            ? (i + count) % source.Length
            : (i + count + source.Length) % source.Length;
        yield return source[j];
    }
}

Answer 3

    static void Main(string[] args)
    {
        string[] nd = Console.ReadLine().Split(' ');
        int n = Convert.ToInt32(nd[0]);
        int d = Convert.ToInt32(nd[1]);
        int[] a = Array.ConvertAll(Console.ReadLine().Split(' '), aTemp => Convert.ToInt32(aTemp));

Don't Repeat Yourself. There's an easy opportunity here to factor out a method which reads an array of integers from stdin.

In general I would prefer to remove the explicit lambda, but I think that in this case just passing Convert.ToInt32 would be ambiguous because of the overloads.

---

        int[] result = rotLeft(a, d);
        Console.WriteLine(string.Join(" ", result));
    }

When implementing a spec, ask yourself what the inputs and the outputs are. As long as you respect those, you should be at liberty to optimise the processing. So it's not actually necessary to rotate the array: just to print the result of rotating it.

        Console.Write(a[d]);
        for (int i = d+1; i < a.Length; i++)
        {
            Console.Write(' ');
            Console.Write(a[i]);
        }
        for (int i = 0; i < d; i++)
        {
            Console.Write(' ');
            Console.Write(a[i]);
        }

---

But I think that that code probably has a bug. Does the spec make any guarantees about the value of d other than that it's an integer? Can it be negative? Can it be greater than n?

Answer 4

You are focusing on the wrong portion of the problem. You're thinking the array needs to be rotated. The output of the array needs to be "rotated" but the array can remain as-is.

So simply write a loop that starts at the middle of the array, incrementing until it hits the end, and then continues along from the beginning until it hits the index just before the one you started at.

The output of that loop is the "rotated" array, from the visibility of the testing framework.

    string sep = "";
    for (int i = d % a.Length; i < a.Length; i++) {
        Console.Write(sep);
        Console.Write(a[i]);
        sep = " ";
    }
    for (int i = 0; i < d % a.Length; i++)
    {
        Console.Write(sep);
        Console.Write(a[i]);
        sep = " ";
    }

This is a great reason why you should sometimes see hackerrank as a poor place to really learn programming.

hackerrank primarily contains programming problems harvested from programming competitions. Competitions where these problems are meant to be solved fast, with a time deadline. This means that the problems are more about building a quick, clever, solution and less about really learning the lessons that would help you in a programming career.

Another example of a solution is

    string sep = "";
    for (int i = d; a.Length + d - i > 0; i++) {
        Console.Write(sep);
        Console.Write(a[i % a.Length]);
        sep = " ";
    }

Which is, according to hackerranks estimation, "just as good" as the above solution, but is far less readable.

Answer 5

Because of the 2 imbricated for loops here:

 for (int intI = 0; intI < d; intI++) {   
   for (int intK = 0; intK < a.Length; intK++) {
               ...
   }
 }

your code performs d * a.Length actions - which takes quadratic time when d is near a.Length/2.

So, we may ask, can we do better ?

The answer is yes. There is a linear-time solution. It is as follows:

1. "mirror" the first d elements
2. mirror the whole array
3. mirror the size-d first elements.

Implementation of mirror (reverse an array) is left to the reader.

Linear time complexity. 0(1) extra room needed (loop variable and temporary for exchange).

So it is clearly an improvement on the original version.

Answer 6

If r = number of rotations, a = int[] array, n = a.length, to rotate the array you need to

1. move a[r to n] to the beginning of the array
2. move a[0 to r] to end of array

Also r can be reduced to r % n, as for every n rotations, the array repeats.

Code:

    int[] result = new int[];
    r = r % n;
    int count = 0;

    for(int i=r;i<n;i++){
        result[count++] = a[i];
    }

    for(int i=0;i<r;i++){
        result[count++] = a[i];
    }

Answer 7

Another solution, with proper justification I hope.

First, we will consider rotating to the right. Not a big deal, because shifting an array (of size n) by d position to the left is the same as shifting it n-d positions to the right. And conversely.

It will just make the explanations easier.

Example : shift an array a of size 21, 6 positions to the right.

Poor a[0], what shall we do with you?

Consider a[0]. It it suppose to move to a[6]. Which moves to a[12]. Pushed into a[18]. Going to a[3] (because 18 + 6 = 24 = 21 + 3), etc.

So we follow a path which goes back to the initial position. It is the cycle (0, 6, 12, 18, 3, 9, 15, 0, 6, ....).

Code for shifting a[0] and friends

Here is the code (C-ish)

int next = 0;
int saved = a[0];
do {
   next = (next + d) % n;
   swap (saved, a[next]);
} while (next != 0);

Here comes the GCD

But there are other cycles. Actually this is linked to the greatest common divisor. There are exactly gcd(d, n) such cycles. And 0,1,...gcd(d,n-1) belong to different cycles.

So they are convenient starting points.

Final code

int nb_cycles = gcd(d, n);

for (int start = 0; start < nb_cycles; start++) {
   int next = start;
   int saved = a[start];
   do {
      next = (next + d) % n;
      swap (saved, a[next]);
   } while (next != start);
}

Complexity

• Linear time, as each element of the array is assigned exactly once.
• In-place, non recursive