Right Rotate Array by N numbers

Theory to get started

In this approach we take double pointers I and J and move them until the end of an array as we come across any index that contains 0.

Step 1: do k = k % n; so that we can get exact estimate of the number of times we need to do rotation, e.g. if someone asks us to rotate an array of length 6 twenty or twenty-five then we can simply do 20 % 6 = 2 times or 25 % 6 = 1

Step 2: Copy the elements that we wish to rotate from the index of rotation denoted by K hence the array would start from n-k. The reason being that these are the only elements that we would wish to rotate, and it will be useful later to paste this array infront of the rest of elements to display the rotation.

Step-3: if pointer J returns -1, that means it just returns the default value and there was no 0th element found in an entire array hence return the array as is.

Step 4: Now run a new loop again but this time the starting point should be J+1 the reason being that anything before 0th element has been already shifted.

Step 5: Print the final array

Continue the steps above until your reach end of an array.

Here is the breakdown of the steps in the code:

/* 
    Given an integer array nums, rotate the array to the 
    right by k steps, where k is non-negative. 
*/
#include <stdio.h>
#include <iostream>
#include <vector>

using namespace std;

vector<int> rightRotateByN(vector<int>& arr, int k){
    int n = arr.size();
    /* step 1 - get correct estimate of rotation */
    k = k % n;
    // no rotation needed if k == 0
    if (k === 0) {
        return arr;
    }
    vector<int> temp(k);
    /* step 2 - copy elems to rotate to temporary array Temp */
    for(int i = n-k; i < n; i++ ){
        temp[i - n + k] = arr[i];
    }    
    /* step 3 - run a reverse array to shift indexes of original array based on k */
    for(int i = n-k-1; i >= 0; i-- ){
        cout << i+k << endl;
        arr[i + k] = arr[i];
    }
    /* step 4 - assign the value stored in temp back to indexes until index k */
    for (int i = 0; i < k; i++){
        arr[i] = temp[i];
    }
    return arr;
}

int main(){
    
    int n, k;
    cin >> n >> k;

    vector<int> arr(n);

    for(int i=0; i < n; i++){
        // take array input from the user
        cin >> arr[i];
    }

    vector<int> arrFinal = rightRotateByN(arr, k);
    
    for(int i=0; i < n; i++){
        // take array input from the user
        cout << arrFinal[i] << " ";
    }
}

[Top]