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 }

Methods to find the solution

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 -

• First, reverse the entire array.
• Modify k modulo k modulo N (array size), because k is greater than N.
• Reverse the first k elements of the array so that they are in order.
• Then reverse the range of the remaining elements, i.e. from k to N-1.
• li>

Example

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;
}

Output

Array after rotating by k-elements : 6 2 4 5 4 6 2 6 43 7 3

Conclusion

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!