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.
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 elementint 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
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:
Note: In this method, the maximum number of times that a single element is shifted is
, whereas in the previous method, it was .
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 >= NreverseArray(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
Free Resources