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: 38Brute 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
ENDImplementation 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
8+ registered 