Home »
Data Structure »
Array Data Structure
Program for array rotation
C++ implementation to rotate an array using multiple approaches.
Submitted by Vikneshwar GK, on February 12, 2022
Consider an integer array of size n and an integer d. The task at hand is to rotate the elements anti-clockwise by d elements, i.e., place the first d elements at the end of the array by pushing the remaining elements to the front.
Example:
Input:
array[]= {5, 2, 4, 8, 3}
d = 3
Output:
array[] = {8, 3, 5, 2, 4}
Input:
array[]= {1, 2, 3, 4, 5, 6}
d = 2
Output:
array[]= {3, 4, 5, 6, 1, 2}
Solution 1: Rotating elements 1 by 1
Rotating the array once means is to rotate the array one time in the anti-clockwise direction, which ultimately denotes d=1. When we use this idea d times, then the array will be rotated accordingly to the given problem statement. It involves the following algorithm:
- Store array[0] in a temporary variable
- Iterate through the array and store array[1] in array[0], array[2] in array[1], and so on
- Assign array[0], which is stored in the temporary variable, in array[n-1]
- Perform the above steps for d times
- Print the array
C++ Implementation:
#include <bits/stdc++.h>
using namespace std;
// Function to rotate the array once
void rotateOnce(int array[], int length)
{
int temp = array[0];
for (int i = 0; i < length - 1; i++)
array[i] = array[i + 1];
array[length - 1] = temp;
}
// Function to perform one rotate
// d times
void rotate(int array[], int d, int length)
{
for (int i = 0; i < d; i++)
rotateOnce(array, length);
}
// Function to print the array
void printArray(int array[], int length)
{
for (int i = 0; i < length; i++)
cout << array[i] << " ";
cout << endl;
}
// Main function
int main()
{
int array[100], N, d;
cout << "Enter Number of elements: ";
cin >> N;
for (int i = 0; i < N; i++) {
cout << "Enter element " << i + 1 << ":";
cin >> array[i];
}
cout << "Enter the value of d: ";
cin >> d;
rotate(array, d, N);
cout << "Rotated Array" << endl;
printArray(array, N);
return 0;
}
Output:
Enter Number of elements: 5
Enter element 1:1
Enter element 2:2
Enter element 3:3
Enter element 4:4
Enter element 5:5
Enter the value of d: 2
Rotated Array
3 4 5 1 2
Time Complexity: O(n * d), where n is the length of the array and d is the rotate count.
Solution 2: Juggling Algorithm
This is a comparatively efficient method that involves rotating the array using a O(nlog(n)) algorithm. The idea here is to divide the array into different sets and the number of sets is the gcd of the length of the array and the rotation count d. Then we rotate the elements, not consecutively, but from one group to another.
Look at the following example.
- If array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9} and d = 3, then GCD of array length and d is 3.
- After 1st iteration, array will become array[] = {4, 2, 3, 7, 5, 6, 1, 8, 9}
- After 2nd iteration, array will become array[] = {4, 5, 3, 7, 8, 6, 1, 2, 9}
- After 3rd iteration, array will become array[] = {4, 5, 6, 7, 8, 9, 1, 2, 3}
C++ implementation:
#include <bits/stdc++.h>
using namespace std;
// Function to find gcd of two number
int findGCD(int num1, int num2)
{
if (num2 == 0)
return num1;
else
return findGCD(num2, num1 % num2);
}
// Function to rotate array in groups
void rotate(int array[], int d, int length)
{
// case to handle when d greater than length
d = d % length;
int gcd = findGCD(d, length);
for (int i = 0; i < gcd; i++) {
// store the first group's element in temp
int temp = array[i];
int j = i;
// rotate elements between groups
while (1) {
int k = j + d;
if (k >= length)
k = k - length;
if (k == i)
break;
array[j] = array[k];
j = k;
}
array[j] = temp;
}
}
// Function to print the array
void printArray(int array[], int length)
{
for (int i = 0; i < length; i++)
cout << array[i] << " ";
cout << endl;
}
// Main function
int main()
{
int array[100], N, d;
cout << "Enter Number of elements: ";
cin >> N;
for (int i = 0; i < N; i++) {
cout << "Enter element " << i + 1 << ":";
cin >> array[i];
}
cout << "Enter the value of d: ";
cin >> d;
rotate(array, d, N);
cout << "Rotated Array" << endl;
printArray(array, N);
return 0;
}
Output:
Enter Number of elements: 9
Enter element 1:5
Enter element 2:10
Enter element 3:15
Enter element 4:20
Enter element 5:25
Enter element 6:30
Enter element 7:35
Enter element 8:40
Enter element 9:45
Enter the value of d: 3
Rotated Array
20 25 30 35 40 45 5 10 15
Time Complexity: O(n), where n is the length of the array.