Rotate array in the right direction by K steps

Brief Description: Given an array A, we have to rotate the array in the right direction by K steps.

Let’s begin with an example.

A = [1,2,3,4,5,6,7,8,9,10] and K = 3, then if we rotate the array in the right direction by K times, the resultant array would look like [8,9,10,1,2,3,4,5,6,7].

Similarly for the same array if K = 13, the resultant array we obtain is the same. That means, if K>N where N = length of the array we can modify K to K%N.

If the resultant array (right rotated array) is denoted by R. Then we have R[ ( i + K ) % N ] = A[ i ].

This is because the i th element of A becomes ( i + K ) th element of R. So to avoid overflows we will use %N. So finally we can conclude that element at A[ ( i + ( N – K ) ) % N] becomes B[ i ].

Code :

#include <iostream>
using namespace std;
int main ()
{
  int A[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
  int K = 13;
  int N = sizeof (A) / sizeof (A[0]);
  K = K % N;
  cout << "Array before rotation : ";
  for (int i = 0; i < N; i++)
    {
      cout << A[i] << " ";
    }
  cout << endl;
  cout << "Array after rotation : ";
  for (int i = 0; i < N; i++)
    {
      cout << A[(i + (N - K)) % N] << " ";
    }
  return 0;
}

Output :

Time Complexity : O(N)

Space Complexity: O(N)

Similar types of problems on coding platforms : https://www.geeksforgeeks.org/reversal-algorithm-right-rotation-array/

https://www.hackerearth.com/practice/data-structures/arrays/1-d/practice-problems/algorithm/monk-and-rotation-3/description/

Check out other C++ Programs : https://www.codesexplorer.com/category/cplusplus