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 1 (ROTATING ONE BY ONE)

## LEFT ROTATION

In this approach, we store the element at index zero i.e arr[0] in a temporary variable say temp and shift arr[1] to arr[0], arr[2] to arr[1], arr[3] to arr[2], ....... , arr[n-1] to arr[n-2] (n is the size of the array) and finally we put temp in arr[n-1].We do this k times where k is the number of times we need to left rotate the array before printing it.

``````#include <bits/stdc++.h>
using namespace std;

//this function left rotates the array of size n by k times
void left_rotate(int arr[],int n,int k)
{
for(int i=0;i<k;i++)
{
int temp=arr[0];
for(int j=0;j<n-1;j++)
{
arr[j]=arr[j+1];
}
arr[n-1]=temp;
}
}

//this function prints 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);   //function to left rotate the array by k times
print_array(arr,n);    //function to print the array elements

return 0;
}``````

For the input :

5 3

1 2 3 4 5

The output will be

4 5 1 2 3

## RIGHT ROTATION

In this approach, we store the element at the last index i.e arr[n-1] in a temporary variable say temp and shift arr[n-2] to arr[n-1], arr[n-3] to arr[n-2], ....... , arr[1] to arr[2] , arr[0] to arr[1] (n is the size of the array) and finally we put temp in arr[0].We do this k times where k is the number of times we need to right rotate the array before printing it.

``````#include <bits/stdc++.h>
using namespace std;

//this function right rotates the array of size n by k times
void right_rotate(int arr[],int n,int k)
{
for(int i=0;i<k;i++)
{
int temp=arr[n-1];
for(int j=n-1;j>0;j--)
{
arr[j]=arr[j-1];
}
arr[0]=temp;
}
}

//this function prints 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);      //function to right rotate the array by k times
print_array(arr,n);          //function to print the array elements

return 0;
}``````

For the input:

5 3

1 2 3 4 5

The output will be

3 4 5 1 2

## TIME COMPLEXITY

The time complexity for this approach is O(n*k) where n is the size of the array and k is the number of times we have to rotate the array.

Discussion

19