Home » Data Structure » Array Data Structure

Queries on Left and Right Circular Shift on the Array

Queries on left and right circular shift on the array, its implementation using C++ program.
Submitted by Vikneshwar GK, on February 26, 2022

Consider an integer array, of size n. There are 3 operations that can be performed on this array:

• 1 x - Rotate the array in a clockwise direction by x times
• 2 y - Rotate the array in an anticlockwise direction by y times
• 3 left right - Calculate the sum of the array index from left to right (both inclusive) and print them

Perform the operations on the array and print the output.

Example:

Input:
n = 5,
array[] = { 1, 2, 3, 4, 5 }

query 1 = { 1, 4 }
query 2 = { 3, 2, 4 }
query 3 = { 2, 3 }
query 4 = { 3, 1, 4 }

Output:
10
10

Explanation:
Initial array[] = { 1, 2, 3, 4, 5 }
After operation 1, array[] = { 2, 3, 4, 5, 1 }.
After operation 2, sum from index 2 to index 4 is 10, so output 10.
After operation 3, array[] = { 5, 1, 2, 3, 4 }.
After operation 4, sum from index 1 to index 
4 is 10, so output 10.

Solution:

Instead of performing every given operation in the input, we can calculate the net rotation and perform the sum operation. It involves the following steps:

• Calculate the sumArray for each element from 0 to element's index, i.e. for array={1, 2, 3}, sumArray is {1, 3, 6}
• Declare a variable, rotationStatus and initialize it to 0
• For Operation 1, i.e., clockwise rotation, subtract the rotation count from rotationSum and perform modulo division by n
• For Operation 2, i.e., anti-clockwise rotation, add the rotation count to rotationSum and perform modulo division by n
• For Operation 3, i.e., calculating sum from left to right
  • calculate appropriate left by adding rotationSum and n to left and modulo divide by n
  • calculate appropriate right by adding roationSum and n to right and modulo divide by n
  • if left<=right, subtract sumArray[right+1] and sumArray[left]
  • else, add sumArray[n] and sumArray[right+1] and subtract sumArray[left] from it
  • Print the result

C++ Implementation:

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

// Function to perform operation 1
void operation1(int* rotationStatus, int rotationCount, int length)
{
    (*rotationStatus) = ((*rotationStatus) - rotationCount) % length;
}

// Function to perform operation 2
void operation2(int* rotationStatus, int rotationCount, int length)
{
    (*rotationStatus) = ((*rotationStatus) + rotationCount) % length;
}

// Function to perform operation 3
void operation3(int rotationStatus, int left, int right,
    int sumArray[], int length)
{
    // Finding absolute l and r.
    left = (left + rotationStatus + length) % length;
    right = (right + rotationStatus + length) % length;

    // if left is before right
    if (left <= right)
        cout << (sumArray[right + 1] - sumArray[left]) << endl;

    // If right is before left
    else
        cout << (sumArray[left] + sumArray[right + 1] - sumArray[left])
             << endl;
}

// function to call the operations
void wrapper(int array[], int length)
{
    int sumArray[length + 1];
    sumArray[0] = 0;

    // Finding sum
    for (int i = 1; i <= length; i++)
        sumArray[i] = sumArray[i - 1] + array[i - 1];

    int rotationStatus = 0;

    // Solving each query
    operation1(&rotationStatus, 3, length);
    operation3(rotationStatus, 0, 2, sumArray, length);
    operation2(&rotationStatus, 1, length);
    operation3(rotationStatus, 1, 4, sumArray, length);
}

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

    for (int i = 0; i < N; i++) {
        cout << "Enter element " << i + 1 << ":";
        cin >> array[i];
    }
 
    wrapper(array, N);
    
    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
12
6