Home > Article > Backend Development > Inversion algorithm for right rotation of array written in C++
In this article we will learn about the reversal algorithm to rotate the given array to the right by k elements like −
Input : arr[ ] = { 4, 6, 2, 6, 43, 7, 3, 7 }, k = 4 Output : { 43, 7, 3, 7, 4, 6, 2, 6 } Explanation : Rotating each element of array by 4-element to the right gives { 43, 7, 3, 7, 4, 6, 2, 6 }. Input : arr[ ] = { 8, 5, 8, 2, 1, 4, 9, 3 }, k = 3 Output : { 4, 9, 3, 8, 5, 8, 2, 1 }
You can easily solve this problem by moving each element to the right and repeating this process k times. But this will take more time as its time complexity is O(k * N).
Inversion algorithm: Inversion is to reverse an array. Rotating an array can be done by reversing certain element ranges. According to this algorithm -
using namespace std; #include <bits/stdc++.h> void reverse(int nums[], int start,int end) { int temp=0; // reversing array with swapping start element with end element. while(start<=end){ temp=nums[end]; nums[end]=nums[start]; nums[start]=temp; start++; end--; } } int main() { int arr[] = {4, 6, 2, 6, 43, 7, 3, 6, 2, 4, 5 }; int N = sizeof(arr)/sizeof(arr[0]); int k = 4; // reversing whole array reverse(arr, 0, N-1); k = k%N; // reversing element range of 0 to k-1. reverse(arr, 0, k-1); // reversing element range of k to last element. reverse(arr, k, N-1); cout << "Array after rotating by k-elements : "; for(int i = 0;i<N;i++) cout << arr[i] << " "; return 0; }
Array after rotating by k-elements : 6 2 4 5 4 6 2 6 43 7 3
In this article we discussed about using inversion algorithm by k The problem of right-rotating the elements of the array. We discussed what the inversion algorithm is and how to implement it to solve this problem. We also discussed C code to solve this problem. We can write this code in any other language like C, Java, Python, etc. Hope this article is helpful to you.
The above is the detailed content of Inversion algorithm for right rotation of array written in C++. For more information, please follow other related articles on the PHP Chinese website!