Program to Right Rotate (Shift) Array by one

Write a Program to Right Rotate (Shift) Array by one.

Example,

Input: 1 2 3 4 5 6
Output: 6 1 2 3 4 5

This problem can be solved in many ways, we will discuss some of them.

Right Rotate Array without swapping

In this method, we overwrite the ith index element with (i-1)th element from Right-To-Left.

But by doing so, we lose the last element of the array. So, we use a temporary variable temp to store the last element of the array.

After we are done overwriting, we set first index of array to temp.

See the illustration for better understanding,

right shift array

Steps

  1. Initialize i = N-1.
  2. Set temp = arr[N-1].
  3. Repeat the following Steps while i > 0
    • a[i] = a[i-1]
    • i = i – 1
  4. Set arr[0] = temp.

Program in c/c++

#include<stdio.h>

void rightRotateArray(int *arr,int n){
	int temp, i;
	temp = arr[n-1];
	for(i=n-1;i>0;--i){
		arr[i] = arr[i-1];
	}
	arr[0] = temp;
}

int main(){
	int arr[100];
	int n,i;
	
	printf("\n\tEnter Size of Array: ");
	scanf("%d",&n);
	
	printf("\n\tEnter Array Elements: ");
	for(i = 0;i<n;++i){
		scanf("%d",&arr[i]);
	}
	
	rightRotateArray(arr,n);
	
	printf("\n\tArray After Right-Rotation by one: ");
	for(i = 0;i<n;++i){
		printf("%d ",arr[i]);
	}
	printf("\n");
}

Output

Right-Rotate Array with Swapping

It can be done in 2 ways

Method 1

In this method, we keep swapping adjacent elements of the array from Right-to-Left. This results in the right-rotation of the array by one.

See the illustration for better understanding,

right rotate array by one swapping 1

Steps

  1. Initialize i = N-1.
  2. Repeat Following Steps while i > 0
    • SWAP(arr[i] , arr[i-1]).
    • i = i – 1.

Program in c/c++

#include<stdio.h>

void rightRotateArray(int *arr,int n){
	int temp;
	for(int i=n-1;i>0;--i){
        // swapping a[i] and a[i-1]
		temp = arr[i];
		arr[i] = arr[i-1];
		arr[i-1] = temp;
	}
}

int main(){
	int arr[100];
	int n,i;
	
	printf("\n\tEnter Size of Array: ");
	scanf("%d",&n);
	
	printf("\n\tEnter Array Elements: ");
	for(i = 0;i<n;++i){
		scanf("%d",&arr[i]);
	}
	
	rightRotateArray(arr,n);
	
	printf("\n\tArray After Right-Rotation by one: ");
	for(i = 0;i<n;++i){
		printf("%d ",arr[i]);
	}
	printf("\n");
}

Output

Method 2

This method is also based on swapping.

But instead of swapping adjacent elements, we swap each index value with the first index value.

The swapping is done from Left-To-Right.

See the following illustration,

right rotate array by one swapping 2

Steps

  1. Initialize i =1.
  2. Repeat the following steps while i < N.
    • SWAP( arr[i] , arr[0] ).
    • i = i + 1.

Program in c/c++

#include<stdio.h>

void rightRotateArray(int *arr,int n){
	int temp,i;
	
	for( i=1; i<n; ++i){
		// swapping a[i] and a[0]
		temp = arr[0];
		arr[0] = arr[i];
		arr[i] = temp;
	}
}

int main(){
	int arr[100];
	int n,i;
	
	printf("\n\tEnter Size of Array: ");
	scanf("%d",&n);
	
	printf("\n\tEnter Array Elements: ");
	for(i = 0;i<n;++i){
		scanf("%d",&arr[i]);
	}
	
	rightRotateArray(arr,n);
	
	printf("\n\tArray After Right-Rotation by one: ");
	for(i = 0;i<n;++i){
		printf("%d ",arr[i]);
	}
	printf("\n");
}

Output

right rotation output 3

Complexity

Time Complexity: O(N)
Space Complexity: O(1)
for all methods.

References

  1. https://en.wikipedia.org/wiki/Array_data_structure
  2. https://en.wikipedia.org/wiki/Right_rotation

What to study next?

  1. Left-Rotate Array by One
  2. Reverse Array
  3. Reverse Linked List

Leave Comment if You face any Problem

Leave a Comment