Array Rotation

Problem Statement

Given an array of elements, the task is to rotate the array to the right by a specified number of positions. For example, consider the array [1, 2, 3, 4, 5] and rotate it to the right by 2 positions. The resulting array would be [4, 5, 1, 2, 3].

Example:

Consider the array [7, 1, 4, 6, 2] and rotate it to the right by 3 positions:

Original Array: [7, 1, 4, 6, 2]
Rotated Array: [4, 6, 2, 7, 1]

Algorithms:

Brute Force Method:

The brute force approach involves repeatedly shifting the elements of the array to the right one position at a time. This is done for the specified number of rotations. While this method is straightforward, its time complexity is O(n * k), where n is the number of elements in the array, and k is the number of rotations.

Reversal Algorithm:

This algorithm involves three steps: reverse the first part of the array, reverse the second part of the array, and finally reverse the entire array. It's complexity is O(n).

Code Implementation

Brute Force Method:

#include <iostream>
using namespace std;

void rotateArray(int arr[], int n, int k) {
    for (int i = 0; i < k; i++) {
        int temp = arr[n - 1];
        for (int j = n - 1; j > 0; j--) {
            arr[j] = arr[j - 1];
        }
        arr[0] = temp;
    }
}

int main() {
    int arr[] = {7, 1, 4, 6, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;

    rotateArray(arr, n, k);

    cout << "Rotated Array: [";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << (i == n - 1 ? "]\n" : ", ");
    }

    return 0;
}

Reversal Algorithms:

#include <iostream>
using namespace std;

void rotateArray(int arr[], int n, int k) {
    for (int i = 0; i < k; i++) {
        int temp = arr[n - 1];
        for (int j = n - 1; j > 0; j--) {
            arr[j] = arr[j - 1];
        }
        arr[0] = temp;
    }
}

int main() {
    int arr[] = {7, 1, 4, 6, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;

    rotateArray(arr, n, k);

    cout << "Rotated Array: [";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << (i == n - 1 ? "]\n" : ", ");
    }

    return 0;
}

Explanation:

reverseArray Function:

void reverseArray(int arr[], int start, int end) {
    while (start < end) {
        swap(arr[start], arr[end]);
        start++;
        end--;
    }
}

• Reverse elements in the array between indices start and end.
• Use a two-pointer approach with a while loop.
• Swaps elements using the swap function.

rotateArray Function:

void rotateArray(int arr[], int n, int k) {
    k = k % n;
    reverseArray(arr, 0, n - 1);
    reverseArray(arr, 0, k - 1);
    reverseArray(arr, k, n - 1);
}

• Takes an array arr, its size n, and the number of positions to rotate k.
• Ensures k is within the range of the array size using the modulo operator.
• Implements the reversal algorithm for array rotation:
  → Reverses the entire array.
  → Reverses the first part of the array (0 to k - 1).
  → Reverses the second part of the array (k to n - 1).

main function:

int main() {
    int arr[] = {7, 1, 4, 6, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;

    rotateArray(arr, n, k);

    cout << "Rotated Array: [";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << (i == n - 1 ? "]\n" : ", ");
    }

    return 0;
}

• Declares an example array arr and calculates its size n.
• Sets the number of positions to rotate k to 2.
• Calls rotateArray with the provided parameters.
• Prints the rotated array using a loop in the main function.

Complexity Analysis

Brute Force Method:

• Time Complexity: O(n * k)
• Space Complexity: O(1)

Reversal Algorithm:

• Time Complexity: O(n)
• Space Complexity: O(1)