Program for Left Rotation (Shift) of Array by one

Write a Program for Left Rotation (Shift) of Array by one.

Example,

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

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

Left Rotation of Array without swapping

This method does not involve swapping.

We overwrite the ith index element with (i+1)th element from Left-To-Right.

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

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

See the illustration for better understanding,

Steps

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

Program in c/c++

#include<stdio.h>

void leftRotateArray(int *arr,int n){
	int temp, i;
	temp = arr[0];
	for(i=0;i<n-1;++i){
		arr[i] = arr[i+1];
	}
	arr[n-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]);
	}
	
	leftRotateArray(arr,n);
	
	printf("\n\tArray After Left-Rotation by one: ");
	for(i = 0;i<n;++i){
		printf("%d ",arr[i]);
	}
	printf("\n");
}


Output

Left-Rotation of Array with Swapping

It can be done in 2 ways

Method 1

In this method, we keep swapping adjacent elements of the array which results in the Left-Rotation of the array by 1.

The swapping is performed from Left-To-Right.

See the illustration for better understanding,

Steps

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

Program in c/c++

#include<stdio.h>

void leftRotateArray(int *arr,int n){
	int temp;
	for(int i=0;i<n-1;++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]);
	}
	
	leftRotateArray(arr,n);
	
	printf("\n\tArray After Left-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 last index value.

The swapping is done from Right-To-Left.

See the following illustration,

Steps

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

Program in c/c++

#include<stdio.h>

void leftRotateArray(int *arr,int n){
	int temp,i;
	
	for( i=n-2; i>=0; --i){
		// swapping a[i] and a[n-1]
		temp = arr[n-1];
		arr[n-1] = 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]);
	}
	
	leftRotateArray(arr,n);
	
	printf("\n\tArray After Left-Rotation by one: ");
	for(i = 0;i<n;++i){
		printf("%d ",arr[i]);
	}
	printf("\n");
}

Output

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/Left_rotation

What to study next?

1. Right-Rotate Array by one
2. Reverse Array
3. Reverse Linked List

Leave Comment if You face any Problem