Home » Data Structure » Array Data Structure

Find element at given index after a number of rotations

C++ implementation to find element at given index after a number of rotations.
Submitted by Vikneshwar GK, on February 27, 2022

Consider an integer array of size n and set of ranges indicating the left and right range to rotate the array in a clockwise direction. The task at hand is to return the element at a given index after performing the rotation operations.

Example:

Input:
array = {1, 2, 3, 4, 5},
rotations = {{0, 2}, {1, 3}, {0, 4}}, and 
index = 2

Output:
Element at index 2 after rotations is: 4

Explanation: 
After {0, 2}, array will become {3, 1, 2, 4, 5}
After {1, 3}, array will become {3, 4, 1, 2, 5}
After {0, 4}, array will become {5, 3, 4, 1, 2}
Now, the element at index 2 is 4.

Solution:

Instead of performing all the rotations on the array and finding the element at the given index, we can process the given set of ranges without rotating the array. It involves the following steps:

• Iterate through the set of ranges in reverse order, that is, from last to first
• If the index is greater than left and lesser than right
• If yes, then check whether the index is equal to left, if so, set index to right, else decrement the index
• Print the array element at index position

Why process the ranges in reverse order?

Since we need the index position after rotating the array, we need to backtrack the steps that we performed on the array. Therefore, we perform the processing in reverse order.

For example, if the array = {1, 2, 3, 4, 5}, rotations = {{0, 2}, {1, 3}, {0, 4}}, and index = 2, then

1. Process {0, 4} and index = 2
   Since. 0<=index<=4, and index!=0, decrement index. Index will become 1
2. Process {1, 3} and index = 1
   Since, 1<=index<=3 and index=1, set index to 3.
3. Process {0, 2} and index=3
   Since, index>=2, do nothing

So the new index is 3 and the element is 4.

Now, look at the array rotations.

After {0, 2}, array will become {3, 1, 2, 4, 5}
After {1, 3}, array will become {3, 4, 1, 2, 5}
After {0, 4}, array will become {5, 3, 4, 1, 2}
Now, the element at index 2 is 4, which is the same as the previous step.

Therefore, we are processing the ranges in reverse order.

C++ Implementation:

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

// Function to perform rotations and find index element
int findElement(int array[], int ranges[][2],
    int rotations, int index)
{
    for (int i = rotations - 1; i >= 0; i--) {
        int left = ranges[i][0];
        int right = ranges[i][1];

        // check left and right condition
        if (left <= index && right >= index) {
            if (index == left)
                index = right;
            else
                index--;
        }
    }

    // Returning new element
    return array[index];
}

// 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 rotations;
    cout << "Enter number of rotations: ";
    cin >> rotations;

    int ranges[rotations][2];
    for (int i = 0; i < rotations; i++) {
        cout << "Rotation " << i + 1 << endl;
        cout << "Enter left: ";
        cin >> ranges[i][0];
        cout << "Enter right: ";
        cin >> ranges[i][1];
    }

    int index;
    cout << "Enter the index: ";
    cin >> index;

    cout << "Element at index " << index << " after rotations is: " << findElement(array, ranges, rotations, index);
    
    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 rotations: 3
Rotation 1
Enter left: 0
Enter right: 2
Rotation 2
Enter left: 1
Enter right: 3
Rotation 3
Enter left: 0
Enter right: 4
Enter the index: 2
Element at index 2 after rotations is: 4