Home » Data Structure » Array Data Structure

Quickly find multiple left rotations of an array

C++ implementation to quickly find multiple left rotations of an array using multiple approaches.
Submitted by Vikneshwar GK, on February 24, 2022

Consider an integer array, of size n, that has distinct elements. The task at hand is to find the left rotations of the array for the given set of k values.

Example:

Input:
array[]= {1, 2, 3, 4, 5}
k1 = 2
k2 = 1
k3 = 3
            
Output: 3 4 5 1 2
2 3 4 5 1
4 5 1 2 3

Input:
array[]= {30, 40, 50, 60, 70}
k1 = 2
k2 = 4

Output:
50 60 70 30 40
70 30 40 50 60

Solution 1: Using Temporary Array

This is a simple approach that involves using a temporary array as we need the original to be unchanged since we perform multiple rotations. It involves following steps:

• Create a temporary array of size 2n
• Iterate through the array and copy the values to the temporary array with two copies
• Perform k%n and print from k%n to k%n+n

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

// Function to copy array values
// to temporary array
void preprocess(int array[], int length, int temp[])
{
    // Store array[] elements at i and i + n
    for (int i = 0; i < length; i++)
        temp[i] = temp[i + length] = array[i];
}

// Function to rotate the array
void leftRotate(int array[], int length, int k, int temp[])
{
    // perform modulo operation
    int start = k % length;

    // Print array after k rotations
    for (int i = start; i < start + length; i++)
        cout << temp[i] << " ";

    cout << endl;
}

// Main function
int main()
{
    int array[100], N, element;
    cout << "Enter Number of elements: ";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cout << "Enter element " << i + 1 << ": ";
        cin >> array[i];
    }

    int k[100], temp[2 * N], n;
    cout << "Enter Number of k elements: ";
    cin >> n;
    for (int i = 0; i < n; i++) {
        cout << "Enter k" << i + 1 << ": ";
        cin >> k[i];
    }

    preprocess(array, N, temp);
    for (int i = 0; i < n; i++) {
        leftRotate(array, N, k[i], temp);
    }

    return 0;
}

Output:

Enter Number of elements: 5
Enter element 1: 2
Enter element 2: 4
Enter element 3: 6
Enter element 4: 8
Enter element 5: 10
Enter Number of k elements: 3
Enter k1: 2
Enter k2: 4
Enter k3: 3
6 8 10 2 4 
10 2 4 6 8 
8 10 2 4 6

Time Complexity: O(n), where n is the length of the array.

Solution 2: Using Modulo Operator

This is a space efficient approach that will not use a temporary array to perform the rotation for multiple k values.

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

// Function to rotate the array
void leftRotate(int array[], int length, int k)
{
    // Print array after k rotations
    for (int i = k; i < k + length; i++)
        cout << array[i % length] << " ";
    cout << endl;
}

// Main function
int main()
{
    int array[100], N, element;

    cout << "Enter Number of elements: ";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cout << "Enter element " << i + 1 << ": ";
        cin >> array[i];
    }

    int k[100], n;

    cout << "Enter Number of k elements: ";
    cin >> n;

    for (int i = 0; i < n; i++) {
        cout << "Enter k" << i + 1 << ": ";
        cin >> k[i];
    }

    for (int i = 0; i < n; i++) {
        leftRotate(array, N, k[i]);
    }

    return 0;
}

Output:

Enter Number of elements: 5
Enter element 1: 1
Enter element 2: 2
Enter element 3: 3
Enter element 4: 4
Enter element 5: 5
Enter Number of k elements: 3
Enter k1: 4
Enter k2: 2
Enter k3: 1
5 1 2 3 4 
3 4 5 1 2 
2 3 4 5 1

Time Complexity: O(n), where n is the length of the array.