Rotate an array

Given an array and a positive integer k, rotate the array k times.
Example:
Array:  1 2 3 4 5
k: 1
Output: 2 3 4 5 1
k: 2
Output: 3 4 5 1 2
k: 3
Output: 4 5 1 2 3

Algorithm

Naive Solution: Rotate array by one element k times
Algorithm to rotate array by one element:
1. Take a temporary variable to store first element of the array.
2. Shift all elements by 1 position on the left, overwriting the first element of the array.
3. Set last element of array to the first element saved in temporary variable.
This is rotation by 1 element.
By invoking this k times, we get array rotated k times.
Time Complexity: O(n*k)
Space Complexity: O(1)

Solution using Temporary Array:
1. Move first k elements of the array to a temporary array.
2. Shift all the elements of the array from k+1 to end of array to the beginning of the array.
3. Copy the k elements in temporary array to the last k positions of the original array.
Time Complexity: O(n)
Space Complexity: O(k)

Efficient Solution: Using Array Reversal
1. Reverse the array elements from 0 to k-1.
2. Reverse the array elements from k to array.length-1.
3. Reverse the whole array.
Example:
1 2 3 4 5
k = 3
Step 1. Reverse the array elements from 0 to 2: 3 2 1 4 5
Step 2. Reverse the array elements from 3 to 4: 3 2 1 5 4
Step 3. Reverse the whole array: 4 5 1 2 3
Time Complexity: O(n)
Space Complexity: O(1)

What happens if k > n?
Example:
array: 1 2 3 4 5
k = 8
Then after 8 rotations, the array will be:
4 5 1 2 3
which is same as rotating the array 3 times (k%n = 8%5 = 3)
If this is not handled in algorithms 2 (using temporary array) and 3 (using array reversal), we get an ArrayIndexOutOfBoundsException.
So, we add following checks on k in all 3 algorithms:
1. If k < 0, throw IllegalArgumentException
2. If k > n, set k = k%n

 

 

Code->

/* function to print an array */
void printArray(int arr[], int size);

/*Fuction to get gcd of a and b*/
int gcd(int a,int b);

/*Function to left rotate arr[] of siz n by d*/
void leftRotate(int arr[], int d, int n)
{
int i, j, k, temp;
for (i = 0; i < gcd(d, n); i++)
{
/* move i-th values of blocks */
temp = arr[i];
j = i;
while(1)
{
k = j + d;
if (k >= n)
k = k - n;
if (k == i)
break;
arr[j] = arr[k];
j = k;
}
arr[j] = temp;
}
}

/*UTILITY FUNCTIONS*/
/* function to print an array */
void printArray(int arr[], int size)
{
int i;
for(i = 0; i < size; i++)
printf("%d ", arr[i]);
}

/*Fuction to get gcd of a and b*/
int gcd(int a,int b)
{
if(b==0)
return a;
else
return gcd(b, a%b);
}

/* Driver program to test above functions */
int main()
{
int arr[] = {1, 2, 3, 4, 5, 6, 7};
leftRotate(arr, 2, 7);
printArray(arr, 7);
getchar();
return 0;
}

 

Leave a Reply

Your email address will not be published. Required fields are marked *

For Inserting code :
Paste your code in the comment form, select it and then click the language link

C | C++ | Java |

*