How to right shift k elements of an array

Problem statement

This problem requires us to shift/rotate a fixed-size array to the right by k positions, where k is a user-determined variable. For example, given an array [1,2,3,4,5], a shift of 3 positions should result in the final state of the array being [3,4,5,1,2] . There are several different ways to achieve this.

A naive solution

One simple solution is to write an algorithm to shift/rotate the array once, and then repeat this a total of k times.

Let's look at the code below:

#include <iostream>
using namespace std;
void shiftArr(int* arr , int n)
{
// Initially: [1 2 3 4 5]
// swapping the first element with the last element
int temp = arr[0];
arr[0] = arr[n-1];
arr[n-1] = temp;
// Now: [5 2 3 4 1]
// swapping the ith element with the last element for the entire length of the array (where i starts from 1)
for(int i=1 ; i<=n-1 ; i++)
{
int temp2 = arr[i];
arr[i] = arr[n-1];
arr[n-1] = temp2;
// Array in each iteration:
// [5 1 3 4 2]
// [5 1 2 4 3]
// [5 1 2 3 4]
}
}
void shiftArrByK(int* arr , int n , int k)
{
for(int i=0 ; i<k%n ; i++) // we take a modulus in case the value of k is >= N
{
shiftArr(arr , n) ;
}
}
int main() {
int arr[] = {1,2,3,4,5};
int size_of_array = 5 ;
int k = 2 ;
cout << "Before shifting: " ;
for(int i=0 ; i<size_of_array ; i++)
{
cout << arr[i] << " " ;
}
cout << endl ;
shiftArrByK(arr , size_of_array , k);
cout << "After shifting: " ;
for(int i=0 ; i<size_of_array ; i++)
{
cout << arr[i] << " " ;
}
cout << endl ;
}

However, this is a very inefficient way to perform this task. In the worst case, it will take O(N2)O(N2) time, where NN is the size of the array. This is because this approach involves moving all the array elements to right-shift the array just once (moving a single element takes O(1)O(1) time, and there are a total of N elements), and we may need to right-shift the elements up to NN times.

An efficient solution

A better approach would be one in which the number of times the elements need to be shifted is minimized. The diagram below depicts this algorithm along with an example:

An algorithm to shift an array to the right by k elements (k=2 in this example).

Note: In this method, the maximum number of times that a single element is shifted is 22, whereas in the previous method, it was NN.

Let's implement this algorithm below:

#include <iostream>
using namespace std;
void reverseArray(int* arr , int low , int high)
{
while(low<high)
{
swap(arr[low] , arr[high]);
low++;
high--;
}
}
void shiftLeftByN(int* arr , int n , int k)
{
k = k%n ; // we take a modulus in case the value of k is >= N
reverseArray(arr , k+1 , n-1);
reverseArray(arr , 0 , k);
reverseArray(arr , 0 , n-1);
}
int main() {
int arr[5] = {1,2,3,4,5} ;
int size_of_array=5 ;
int k=2 ;
cout << "Before rotation: " ;
for(int i=0 ; i<size_of_array ; i++)
{
cout << arr[i] << " " ;
}
cout << endl ;
shiftLeftByN(arr , size_of_array , k) ;
cout << "After rotation: " ;
for(int i=0 ; i<size_of_array ; i++)
{
cout << arr[i] << " " ;
}
cout << endl ;
}

This method takes O(N)O(N) time in the worst case. This is because it involves reversing the whole array and reversing 2 sub-arrays once each. That makes a total of 3 reversals, and each reversal takes O(N)O(N) time. Therefore, this method provides the most efficient way to right shift k elements of an array.

Free Resources

Copyright ©2025 Educative, Inc. All rights reserved