ARRAY ROTATION

This is a beginner level lab that deals with various approaches to solve questions related to array rotations.

## WHAT WILL YOU LEARN:

• Left rotation of arrays
• Right rotation of arrays
• Various approaches to rotate arrays along with their time complexities

## PRE-REQUISITES:

Basic knowledge of arrays and C++.

Lets get started

APPROACH 2 (REVERSAL ALGORITHM FOR RIGHT ROTATION)

## RIGHT ROTATION

For right rotation also we divide the array into two parts but here the first part is from arr[0] to arr[n-k-1] , the second part is from arr[n-k] to arr[n-1]. We reverse both the parts of the array and then reverse the entire array to get the desired output.

• Lets say the array is 1 2 3 4 5 and k is 3.
• The first part is from arr[0] to arr[1] i.e from element 1 to 2.
• If we reverse the first part, our array will look like this

2 1 3 4 5

• The second part of the array is from arr[2] to arr[4] i.e from element 3 to 5.
• If we reverse the second part, our array will look like this

2 1 5 4 3

• So now our array is 2 1 5 4 3. Upon reversing the entire array we get 3 4 5 1 2 which is the desired output.

``````#include <iostream>
using namespace std;

//function to reverse the array from start to end
void reverse(int arr[],int start,int end)
{
while(start<end)
{
int temp=arr[start];
arr[start]=arr[end];
arr[end]=temp;
start++;
end--;
}
}

//function to right rotate the array of size n by k times
void right_rotate(int arr[],int n,int k)
{
if(k==0)
return;

k=k%n;

reverse(arr,0,n-k-1);
reverse(arr,n-k,n-1);
reverse(arr,0,n-1);
}

//function to print all the elements of the array
void print_array(int arr[],int n)
{
for(int i=0;i<n;i++)
cout<<arr[i]<<" ";
}

int main()
{
int n,k;
cin>>n>>k;
int arr[n];
for(int i=0;i<n;i++)
cin>>arr[i];
right_rotate(arr,n,k);
print_array(arr,n);

return 0;
}``````

## TIME COMPLEXITY

The time complexity for this approach is O(n)

Discussion

19