## Introduction

This blog will try to strengthen our understanding of a single-dimensional 'Array' data structure problem based on circular shift. We will try to understand how to approach any array data structure problem through that problem. The examples presented will help you clear your concepts, a detailed algorithm will provide you with an immediate solution, and the implementation part will give you a thorough understanding of every step. So, let's get started with the problem statement of the circular shift problem and some quick examples.

### Problem statement

Firstly, we will have a look at what precisely the problem says.

Given an array of 'n' elements. In that Array, we have to operate queries on the left and right circular shift on the Array.

We can perform the following operations on the array:

1. Right Shift: We can right shift array n times depending on input. If an array is arr[0], arr[1],...., arr[n â€“ 1], it will become arr[n â€“ 1], arr[0], arr[1],...., arr[n â€“ 2] after one right circular shift.

2. Left Shift: We can left shift array n times depending on the input. If an array is arr[0], arr[1],...., arr[n â€“ 1], it will become arr[1], arr[2], arr[3],...., arr[0] after one left circular shift.

3. Sum from left to right: Print the sum of all the integers in the arr[left...right] subarray (left and right inclusive).

### Sample Examples

Example 1:

**Input:**

```
n=5, q=4, arr={3, 5, 7, 9, 11}
Queries:
q1={1,4} perform right shift 4 times
q2={3,0,3} get sum of elements from 0â€™th to 3â€™rd index
q3={2,3} perform left shit 3 times
q4={3,1,3} get sum of elemnts from 1â€™st to 3â€™rd index
```

**Output:**

```
The answer for second query of finding sum: 32
The answer for fourth query of finding sum: 15
```

Example 2:

**Input:**

```
n=5, q=2, arr[]={8, 15, 17, 19, 11}
Queries:
q1={1,3} perform right shift 3 times
q2={3,0,2} get sum from 0â€™th to 2â€™nd index
q3={2,1} perform left shift 1 time
q2={3,0,2} get sum from 0'th to 2'nd index
```

**Output:**

```
The answer for second query of finding sum: 47
The answer for fourth query of finding sum: 38
```

## Brute Force Approach

In the brute force approach, we will perform the given queries of the circular shift problem in the defined order as directed by the input mentioned in the problem statement. This approach has a time complexity of (N*Q), where N is the number of elements and Q is the number of queries.

### Pseudocode

```
START
N: INPUT "Enter value of the number of elements."
Q: INPUT "Enter the value of the number of queries."
Arr: INPUT "Enter the array elements."
WHILE Q:
INPUT type of query.
Query 1: Right rotation x times
Query 2: Left Rotation x time
Query 3: Sum when query 3 is called.
PRINT Sum
Return
END
```

### Implementation in C++

```
#include <bits/stdc++.h>
using namespace std;
int main()
{
// taking input for n and q
int n, q;
cin >> n >> q;
cout << "Value of n and q are :"
<< " ";
cout << n << " " << q << endl;
// taking input for array
int a[n];
cout << "Initial array:"
<< " ";
for (int i = 0; i < n; i++)
{
cin >> a[i];
cout << a[i] << " ";
}
cout << endl;
// handeling queries
for (int i = 0; i < q; i++)
{
// input for type of queries
int t, x;
cin >> t;
int b[n];
for (int j = 0; j < n; j++)
{
b[j] = a[j];
}
if (t == 1)
{
// handeling query type 1
cin >> x;
int k = 0, j = x;
while (j < n)
{
b[j++] = a[k++];
}
for (int j = 0; j < x; j++)
{
b[j] = a[k];
k++;
}
for (int j = 0; j < n; j++)
{
a[j] = b[j];
}
}
else if (t == 2)
{
// handeling query type 2
cin >> x;
int k = x - 1;
int j = n - 1;
while (k >= 0)
{
b[j--] = a[k--];
}
k = x;
for (j = 0; k < n; j++)
{
b[j] = a[k++];
}
for (int j = 0; j < n; j++)
{
a[j] = b[j];
}
}
else
{
// handeling query type3
int l, r;
cin >> l >> r;
int sum = 0;
for (int j = l; j <= r; j++)
{
sum += a[j];
}
cout << "Sum after query 3: " << sum << endl;
}
}
return 0;
}
```

**Input:**

```
n=5, q=4
arr[]={8, 15, 17, 19, 11}
q1={1, 3}
q2={3, 0, 2}
q3={2, 3}
q4={3, 1, 4}
```

**Output:**

```
Value of n and q are: 5 4
Initial array: 8 15 17 19 11
Sum after query 3: 47
Sum after query 5: 62
```

**Complexity analysis**

**Time complexity**

The time complexity O(N*Q), where N is the size of the Array and Q is the number of queries as we traverse the array Q times with the array's length being N.

**Space complexity**

O(N) will be the space complexity as we have taken an extra array for rotation.

Also see, __Morris Traversal for Inorder__ and __Rabin Karp Algorithm__