Kdtyjb

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?

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.

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];

    }

}

    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?

1. "mirror" the first d elements


2. mirror the whole array


3. mirror the size-d first elements.

In place. Linear time complexity. 0(1) extra room needed.