Rotate Array Elements by D Positions
“Rotate Array Elements by ‘D’ Positions” is one of the most favorite technical interview problem based on array data structure. Here, we are given an array with ‘n’ elements and a ‘d’ value. Our task is to write a program to rotate the given array by ‘d’ positions in clock wise manner.
Example (Rotate Array Elements by D Positions):
Given Array
Arr[] = {34, 67 11, 23, 78, 89}
Rotating Array by 2 places
Arr[] = {11, 23, 78, 89, 34, 67}
There are multiple methods to rotate array by ‘D’ positions. Some of them are:
METHOD 1: Brute-Force Method to Rotate Array by D positions
The simplest solution to rotate array by ‘D’ positions is to run two nested loops. Rotate(Shift the array elements) the position of each element of array by ‘D’ times. The time complexity of this solution is O(n^2), where ‘n’ is the size of the array.
C++ Program to Rotate Array by ‘D’ position is as follows:
/* C++ Program to Rotate Array */
#include<bits/stdc++.h>
using namespace std;
void printArray(int arr[],int n)
{
for(int i = 0 ; i < n ; i++)
{
cout<<arr[i]<<" ";
}
cout<<endl;
}
void rotateArray(int arr[],int n,int D)
{
// Rotate 'D' times
for(int k = 1 ; k <= D ; k++)
{
//store the first element in temporary variable
int temp = arr[0];
// Shifting Elements by one Elements
for(int i = 1 ; i < n ; i++)
{
arr[i-1] = arr[i];
}
// Assign the temporary variable to last index
arr[n-1] = temp;
}
}
int main()
{
int arr[5] = {78, 89, 34, 11, 23};
cout<<"Array Before Rotating:\n";
printArray(arr,5);
cout<<"Rotate the array by two places!!";
rotateArray(arr,5,2);
cout<<"\nArray After Rotating:\n";
printArray(arr,5);
}
OUTPUT: Array Before Rotating: 78 89 34 11 23 Rotate the array by two places!! Array After Rotating: 34 11 23 78 89
METHOD 2: Efficient with Extra Space
The steps required to rotate array by ‘D’ position are as follows:
- The efficient method would to create a temporary array of same size ‘n’.
- Now, copy array elements from position ‘d’ to ‘n-1’ into temporary array from position ‘0’ to ‘n-d’.
- Now, copy the array elements from position ‘0’ to ‘d-1’ into temporary array from position ‘n-d+1’ to ‘n-1’.
- Now, copy all the elements of temporary array to original array.
The time complexity of this solution is O(n), where ‘n’ is the size of array.
C++ Program to rotate Array by ‘d’ Elements is as follows:
/* C++ Program to rotate Array */
#include<bits/stdc++.h>
using namespace std;
void printArray(int arr[],int n)
{
for(int i = 0 ; i < n ; i++)
{
cout<<arr[i]<<" ";
}
cout<<endl;
}
void rotateArray(int arr[],int n,int D)
{
int temp[n];
int index = 0;
// Copy the Elements from index 'D' to 'n-1'
for(int i = D ; i < n ; i++)
{
temp[index] = arr[i];
index++;
}
// Copy the Elements from '0' to 'D-1'
for(int i = 0 ; i < D ; i++)
{
temp[index] = arr[i];
index++;
}
// Copy back the Elements back to
for(int i = 0 ; i < n ; i++)
{
arr[i] = temp[i];
}
}
int main()
{
int arr[5] = {78, 89, 34, 11, 23};
cout<<"Array Before Rotating:\n";
printArray(arr,5);
cout<<"Rotating Array by two positions!!";
rotateArray(arr,5,2);
cout<<"\nArray After Rotating:\n";
printArray(arr,5);
}
OUTPUT: Array Before Rotating: 78 89 34 11 23 Rotate the array by two places!! Array After Rotating: 34 11 23 78 89
METHOD 3: In-place Reversal Method to Rotate Array by D positions
This is little tricky solution, but solves the problem in O(n) time complexity and without extra space.
The steps required to rotate array elements by ‘D’ Elements are as follows:
- Reverse the array from position 0 to ‘D-1’.
- Reverse an array from position ‘D’ to ‘n-1’.
- Reverse whole Array.
Rotate Array
C++ Program to rotate array by ‘d’ positions is as follows:
/* C++ Program to Rotate Array */
#include<bits/stdc++.h>
using namespace std;
void printArray(int arr[],int n)
{
for(int i = 0 ; i < n ; i++)
{
cout<<arr[i]<<" ";
}
cout<<endl;
}
void reverseArray(int arr[],int start,int end)
{
for(int i = start, j = end ; j>i; i++,j--)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
void rotateArray(int arr[],int n,int D)
{
// Reverse an array from '0' to 'D-1'
reverseArray(arr,0,D-1);
// Reverse an array from 'D' to 'n-1'
reverseArray(arr,D,n-1);
// Reverse a whole Array
reverseArray(arr,0,n-1);
}
int main()
{
int arr[5] = {23, 44, 67, 89, 45};
cout<<"Array Before Rotating:\n";
printArray(arr,5);
cout<<"Rotating Array by 2 positions!!";
rotateArray(arr,5,2);
cout<<"\nArray After Rotating:\n";
printArray(arr,5);
}
OUTPUT: Array Before Rotating: 23 44 67 89 45 Rotating Array by 2 positions!! Array After Rotating: 67 89 45 23 44
Related Posts:
- Program to find most frequent element in an array.
- Program to find pair in an array with given sum.
- Program to find first repeating element of an array.
- Program to merge two sorted arrays.
- Program to find missing number in an array.
- Program to sort if array is sorted.
- Program to print Alternate Elements of an Array.
- Program to swap kth element from beginning to kth element from end in an Array.
- Program to print all possible subarrays of the given array.
- Program to print kth smallest and kth largest element of an Array.
- Program to find equilibrium index of an Array.
- Program to find majority element of an Array.
- Program to find mean of the Array.
- Program to sort an Array of 0s and 1s.
- Program to Check if String is alphabetic or numeric or alpha-numeric.
- Program to copy One Character Array to Another.
- Program to Concatenate Two Character Arrays.
- Program to Check whether given String is Palindrome or not.
- Program to convert lower-case alphabet to upper-case alphabet and vice-versa.
- Program to count total number of words in a string.
