17
\$\begingroup\$

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?

\$\endgroup\$
10
  • 6
    \$\begingroup\$ The best code is no code at all. Do you actually need to rotate the array, or just print the elements in rotated order? Because if that’s the case then you can save a whole lot of copying around. \$\endgroup\$ Mar 4, 2019 at 12:45
  • 8
    \$\begingroup\$ @Caramiriel, you've got the wrong box. The one for answers is further down the page. \$\endgroup\$ Mar 4, 2019 at 14:32
  • 1
    \$\begingroup\$ @Caramiriel this isn't O(n) because Skip is not clever... as far as I know it iterates the collection to skip the items. \$\endgroup\$
    – t3chb0t
    Mar 4, 2019 at 16:00
  • 4
    \$\begingroup\$ @t3chb0t Even if it goes through the array twice, 2n, or 200n for that matter, is still O(n) \$\endgroup\$ Mar 4, 2019 at 18:09
  • 1
    \$\begingroup\$ @t3chb0t See the canonical answer on What is BigO? When n is 10, 2n is 20 and n^2 is 100... and it only gets worse the larger n gets. That's why. If n is 2 million, then 200n is 400 million and n^2 is 4 trillion... still ten thousand times larger: what the 200n version can do in 1 minute, it will take almost a week (6.94 days) to run at n^2... and that's before you run into memory issues. That's why BigO works the way it does. \$\endgroup\$ Mar 5, 2019 at 19:13

7 Answers 7

18
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ Great answer. However, if the number of rotations d is as large or greater than the size of array, you'll get out of bounds errors. A quick check at the top could be: if (d >= a.Length) d = d % a.Length; \$\endgroup\$
    – mikeDOTexe
    Dec 12, 2019 at 17:55
17
\$\begingroup\$

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];
    }
}
\$\endgroup\$
5
  • 11
    \$\begingroup\$ In fact, a general tip for programming challenges like this is that, whenever the challenge says "repeat this operation N times," it almost always actually means "find a faster way to get the same result as if you'd repeated the operation N times." That's because the challenges are meant to be challenging, and just writing a for loop to run the same code multiple times is really no challenge at all. \$\endgroup\$ Mar 4, 2019 at 10:00
  • \$\begingroup\$ % is typically slow; and i+count can't wrap more than once. So really you just need a conditional subtract. If you're actually copying the array, hopefully the compiler can split it into two loops that simply copy the 1st / 2nd parts of the array without doing a bunch of expensive per-index calculation, like Henrik's answer. Also hopefully the compiler will hoist the count>0 check out of the loop. \$\endgroup\$ Mar 4, 2019 at 10:02
  • 8
    \$\begingroup\$ @PeterCordes - I think % is clearer and never so slow as to justify such an optimization without profiling first. I would be very surprised if it were the bottleneck in application software, rather than, say, disk IO. \$\endgroup\$ Mar 4, 2019 at 10:41
  • \$\begingroup\$ In C, a simplistic microbenchmark doing just a modulo increment shows that it's about 6x slower on a Haswell CPU. is it better to avoid using the mod operator when possible?. Most things aren't a big deal, but integer division is slow unless it's by a compile-time constant that the compiler can turn into a multiply+shift. The OP already said that their solution for rotating an array was too slow rotating 1 element at a time, so presumably a factor of 6 (or more if the compiler can turn it into 2x memcpy) could matter. \$\endgroup\$ Mar 4, 2019 at 22:05
  • 3
    \$\begingroup\$ You can hoist the count > 0 check out of the loop by calculating the left-rotate count once. if(count < 0) count += source.Length; Then the loop becomes much more readable, and probably more efficient unless the compiler already managed to do that for you. \$\endgroup\$ Mar 4, 2019 at 22:14
9
\$\begingroup\$
    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?

\$\endgroup\$
4
  • \$\begingroup\$ Most of the I/O code is provided as part of the challenge. The only thing OP has to provide is the code inside the rotLeft function, which should return the rotated array. \$\endgroup\$
    – jcaron
    Mar 4, 2019 at 11:50
  • \$\begingroup\$ @jcaron, it's OP's responsibility to ask only about their own code. The help centre is quite explicit that any aspect of the code posted is fair game for feedback and criticism. \$\endgroup\$ Mar 4, 2019 at 13:01
  • \$\begingroup\$ The constraints say that 1 <= d <= n, so yes, we have guarantees about d. \$\endgroup\$
    – Astrinus
    Mar 5, 2019 at 8:12
  • 1
    \$\begingroup\$ @Astrinus, if I wanted answers to those questions I'd have posted them as comments on the question. As I see it, one of the things a code review should do is challenge OP to think about whether they've fully understood the spec, and whether they can update the code if the spec (or their understanding of it) changes. \$\endgroup\$ Mar 5, 2019 at 8:30
4
\$\begingroup\$

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.

\$\endgroup\$
11
  • 1
    \$\begingroup\$ Well one thing one should certainly learn from this challenge is what string.Join does and how it avoids the rather awful for loop :) (The given solution also misses some necessary modulo ops) \$\endgroup\$
    – Voo
    Mar 4, 2019 at 19:21
  • \$\begingroup\$ @Voo Out of curiosity, which modulo does this miss? I know I wrote it by hand without the aid of a computer, but the loop (in my 5 element example, starting at index 3 would be 3, 4, 5, 6, 7 (8 would be 5 + 3 - 8, so it wouldn't get there). and 3 % 5 = 3, 4 % 5 = 4, 5 % 5 = 0, 6 % 5 = 1, 7 % 5 = 2. Now, I just might have a bug in there after all; but, maybe not, which is a perfect example of why writing it this way is less than ideal and why hackerranks fascination with programming competitions as question banks is bad. \$\endgroup\$
    – Edwin Buck
    Mar 4, 2019 at 20:20
  • 2
    \$\begingroup\$ You're supposed to do n rotations. Nowhere does it say that n < arr.Length. You could have an array of 1,2,3 and d=5. Both of your solutions fail with an out of bounds there. \$\endgroup\$
    – Voo
    Mar 4, 2019 at 21:14
  • 1
    \$\begingroup\$ @Voo: if you read the challenge, you see that 1 <= d <= n, i.e. rotate an n elements array by d steps, so you cannot have more rotations than elements. \$\endgroup\$
    – Astrinus
    Mar 5, 2019 at 8:15
  • \$\begingroup\$ @Voo I think you keep focusing on how (in my latter example) i is often out-of-range of the array. That's probably why you keep saying "out of bounds" which would cause an error if I was pulling out the i element of the array. But I'm not pulling i out of the array, I'm pulling i % a.Length which can't be out of bounds. \$\endgroup\$
    – Edwin Buck
    Mar 5, 2019 at 17:10
3
\$\begingroup\$

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.

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

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];
    }
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$

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