CODEWITHSUNDEEP
c#arraysrotation
Uladz Kha
Uladz Kha

Reputation: 2354

A left rotation operation on an array of size n shifts

I try to implement a left rotation on an array of size n shifts. For example, I have

array = {1,2,3,4,5};

and I have number of shifts:

shifts = 2;

After processing the array it has to look like this:

array = {3,4,5,1,2};

I have implemented it with two for loops:

var array = new int[]{1,2,3,4,5};
var shifts =3;
var temp = 0;
for(var j = 0; j < shifts; j++){
     temp = array[0];
     for(var i = 0; i < array.Length -1; i++){
         array[i] = array[i + 1];
     }
     array[array.Length-1] = temp;
}
for(var i =0 ; i< array.Length; i++){
    System.Console.Write(array[i]+ " ");
}
 Console.Read();

And it is working, but it isn't passing some tests with big amount of numbers in array and I get Terminated due to timeout error;

Are there any ways to implements left rotation in one loop?

Upvotes: 1

Views: 336

Answers (4)

shaik nadeem
shaik nadeem

Reputation: 1

import java.util.*;
 public class ArrayRotation{
     public static void main(String[] args) {
         Scanner sc=new Scanner(System.in);
         System.out.println("enter size of array:");
         int n=sc.nextInt();                                         
         int arr[]=new int[n];
         System.out.println("enter elements:");
         for(int i=0;i<n;i++)
         arr[i]=sc.nextInt();
         System.out.println("enter shifts:");
         int d=sc.nextInt();
         int arr1[]=new int[d];
         for(int i=0;i<d;i++)
         arr1[i]=arr[i];
        System.out.println("Array after rotating");
        for(int i=d;i<n;i++)
          System.out.print(arr[i]+" ");
        for(int i=0;i<d;i++)
         System.out.print(arr1[i]+" ");
}

}

Upvotes: 0

Jesse de Wit
Jesse de Wit

Reputation: 4177

Got it to work using a rotating buffer with the size of the amount of shifts.

static void ShiftLeft(int[] array, int shifts)
{
    int length = array.Length;
    int actualShifts = shifts % length;
    if (actualShifts == 0) return;
    int[] buffer = new int[actualShifts];
    Array.Copy(array, buffer, actualShifts);
    int indexAddition = actualShifts - (length % actualShifts);
    for (int i = length - 1; i >= 0; i--)
    {
        int current = array[i];
        int bufferIndex = (i + indexAddition) % actualShifts;
        array[i] = buffer[bufferIndex];
        buffer[bufferIndex] = current;
    }
}

EDIT: As pointed out by @canton7, the circular buffer adds unnecessary complexity. Below should do, basically @canton7's answer, although @canton7 his answer is still more efficient due to the smaller buffer:

int length = array.Length;
int actualShifts = shifts % length;
if (actualShifts == 0) return;
int[] buffer = new int[actualShifts];
Array.Copy(array, buffer, actualShifts);
Array.Copy(array, actualShifts, array, 0, length - actualShifts);
Array.Copy(buffer, 0, array, length - actualShifts, actualShifts);

Upvotes: 0

Patrick
Patrick

Reputation: 419

This is cheating, but a LINQ solution could be:

var array = Enumerable.Range(0, 100).ToArray();
var shiftBy = 2;
var shifted = array.Skip(shiftBy).Concat(array.Take(shiftBy)).ToArray();

If your task is simply 'viewing' the array in this transformed way, to avoid creating a new array, exclude the end .ToArray() and iterate over the IEnumerable<int> directly.

Upvotes: 2

canton7
canton7

Reputation: 42225

I think this as efficient as you'll get for rotating an array in-place. Works for both left and right rotations, depending on the sign of rotateBy:

private static void Rotate<T>(T[] array, int rotateBy)
{
    rotateBy %= array.Length;
    // Nothing to do?
    if (rotateBy == 0)
        return;
    // Normalize it to a right rotation
    if (rotateBy < 0)
        rotateBy = array.Length + rotateBy;
    // Allocate the smallest possible temp array
    if (rotateBy > array.Length / 2)
    {
        T[] temp = new T[array.Length - rotateBy];
        Array.Copy(array, 0, temp, 0, array.Length - rotateBy);
        Array.Copy(array, array.Length - rotateBy, array, 0, rotateBy);
        Array.Copy(temp, 0, array, rotateBy, array.Length - rotateBy);
    }
    else
    {
        T[] temp = new T[rotateBy];
        Array.Copy(array, array.Length - rotateBy, temp, 0, rotateBy);
        Array.Copy(array, 0, array, rotateBy, array.Length - rotateBy);
        Array.Copy(temp, 0, array, 0, rotateBy);  
    }
}

Upvotes: 3

Related Questions