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 LEFT ROTATION)

## LEFT ROTATION

In this approach we divide the array into two parts, the first part is from arr to arr[k-1] ,the second part is from k to 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 to arr i.e from element 1 to 3.
• If we reverse the first part, our array will look like this

3 2 1 4 5

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

3 2 1 5 4

• So now our array is 3 2 1 5 4. Upon reversing the entire array we get 4 5 1 2 3 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 left rotate the array of size n by k times
void left_rotate(int arr[],int n,int k)
{
if(k==0)
return;

k=k%n;

reverse(arr,0,k-1);
reverse(arr,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];
left_rotate(arr,n,k);
print_array(arr,n);

return 0;
}``````

We do k=k%n inorder to deal with cases where k is greater than n.

Discussion

19