CODEWITHSUNDEEP
c#arraysrotation
Team. Coco
Team. Coco

Reputation: 221

Timeout issues in Array rotation. What is so slow about this solution?

I'm doing a question on Hackerrank that is supposed to left shift an array by a certain number of rotations. For example:

1 2 3 4 5 -> 2 3 4 5 1

After a single rotation. This will be done however many times the test case asks for.

Here is my code:

    using System;
    using System.Collections.Generic;
    using System.IO;
    class Solution {
        static void Main(String[] args) {
            /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution */
            string[] firstLine = Console.ReadLine().Split(' ');     
            int numInts = Convert.ToInt32(firstLine[0]);               //Number of ints in list
            int rotations = Convert.ToInt32(firstLine[1]);             //number of left rotations
            int[] numList = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);    //the list to rotate

            for(int i = 0; i < rotations; i++){
                int[] newArray = new int[numList.Length];
                Array.Copy(numList, 1, newArray, 0, numList.Length-1);           //copy from index 1 to end
                newArray[numList.Length-1] =  numList[0];               //end should equal first elem in old array
                Array.Copy(newArray, numList, numList.Length);
            }


            foreach(var i in numList){
                Console.Write(i + " ");
            }
        }
    }

I am passing almost all the tests, but am getting timeout issues on the last 2. What exactly is so slow about this solution that i came up with?

Here is a link to the problem if you want more info: https://www.hackerrank.com/challenges/array-left-rotation/problem

Upvotes: 0

Views: 466

Answers (3)

user2238022
user2238022

Reputation: 39

     - Array a has n number of elements
     - d variable used for number of left rotations


    static int[] rotLeft(int[] a, int d) {
                int l = a.Length, c = 0;
// if the array length is same as number of rotations not need to rotate the array. //we can return the same array as end result would be same
                if( l == d)
                    return a;
// if array length is less the no of rotations, Here I am finding the reminder as //we can skip the l ( length of the array ) rotations as l rotations will give you the same array. //Now just rotate it to the new value d rotations to get the end result.              
                if ( l < d) 
                    d = d % l;


                int[] copy = new int[a.Length];
    //In first loop I am copying values of array "a" from d to end of the array
                for(int j=d; j< a.Length; j++)
                {
                    copy[c] = a[j];
                    c++;
                }
    // Here I am appending the copy array values form 0 to start no of rotations
                for(int i=0;i < d; i++ )
                {
                    copy[c]= a[i];
                    c++;
                }
                // End result would be the result
                return copy;
            }

Upvotes: 0

Tanveer Badar
Tanveer Badar

Reputation: 5524

You should realize that if you start reading an array from index n, it means it has been rotated n % length times. With this inference in mind, your entire program can be simplified into

  using System;
  using System.Collections.Generic;
  using System.IO;

  class Solution 
  {
      static void Main(String[] args) 
      {
            string[] firstLine = Console.ReadLine().Split(' ');     
            int numInts = Convert.ToInt32(firstLine[0]);               //Number of ints in list
            int rotations = Convert.ToInt32(firstLine[1]);             //number of left rotations
            int[] numList = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);    //the list to rotate

           for( var i = 0 ; i < numInts ; ++i )
               Console.WriteLine( numList [ (i + rotations) % numInts ] );
        }
    }

Upvotes: 2

Piotr
Piotr

Reputation: 1177

You have too many copies of an array, which takes time. I think that int.parse at the beginning is also unneeded. You shouldn't literally create copy of array after each rotation but rather calculate position of each element after last rotation (calculate how many steps)

Here is example working solution:

int rotations = 22222222;             //number of left rotations
string[] numList = "5 1 2 4 3".Split(' ');    //the list to rotate

var index = rotations % numInts;
var indexesToWrite = Enumerable.Range(index, numInts - index).Concat(Enumerable.Range(0, index));

foreach (var indexToWrite in indexesToWrite)
{
    Console.Write(numList.ElementAt(indexToWrite) + " ");
}

To clarify the code - it is obvious (as other noticed) that each [numInts] time after we rotate we are getting back to star state. So this obviously leads us to a conclusion, that only remainder after dividing is crucial. After that, we must decide what the result of the % operator would be. In fact, this is information where to start (index of the array) "reading" the numList array. After we reach to an end of the table we should read from the beginning of the numList array (index = 0) till the index where we started to read.

Upvotes: 0

Related Questions