1.
Introduction
1.1.
Problem statement
1.2.
Sample Examples
2.
Brute Force Approach
2.1.
Pseudocode
2.2.
Implementation in C++
2.2.1.
Complexity analysis
3.
Optimized Approach
3.1.
Algorithm
3.2.
Implementation in C++
3.2.1.
Complexity analysis
4.
4.1.
Can we change the size of the array at runtime?
4.2.
How useful is an array in solving programming problems?
4.3.
What is the major drawback of array data structure?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

# Queries on Left and Right Circular shift on Array

Tarun Singh
0 upvote

## 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

## Optimized Approach

We will focus on optimizing the above code of circular shift. Net rotation will be calculated instead of what we did with brute force. We will keep track of net rotation until query 3 is called upon. We will solve for query 3 depending upon whether the rotation is negative or positive. All three steps take constant time; we maintain a prefix array that will calculate the sum, taking O(N) extra space.

### Algorithm

1. Take the input for the size of the Array and the number of queries.

2. We define a prefix array of size N+1, N being the size of the Array.

3. Fill the values for the pref array

``````for (int i = 1; i <= n; i++)
{

pref[i] = pref[i - 1] + a[i - 1];

}``````

4. Maintain a current variable and initialize it to zero.

5. We define a loop for the queries to address

6. In the loop, take input for the type of query{type 1, type 2, type3}.

7. We perform three different operations depending on the query type.

``````If type 1: take input for no of rotation
curr = (curr - x) % n;
If type 2: take input for no of rotation
curr = (curr + x) % n;
If type 3: take input for the left and right positions to calculate the sum.
l = (l + curr + n) % n;
r = (r + curr + n) % n;

If l is less than r
cout
<< (pref[r + 1] - pref[l]) << endl;
If r is less than l
cout
<< (pref[n] + pref[r + 1] - pref[l])
<< endl;``````

8. End of the algorithm.

### 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;
int pref[n + 1];
pref[0] = 0;
int curr = 0;
for (int i = 1; i <= n; i++)
{
pref[i] = pref[i - 1] + a[i - 1];
}

// handeling queries
for (int i = 0; i < q; i++)
{ // input for type of queries
int t, x;
cin >> t;

if (t == 1)
{ // handeling query type 1
cin >> x;
curr = (curr - x) % n;
}
else if (t == 2)
{ // handeling query type 2
cin >> x;
curr = (curr + x) % n;
}
else
{ // handeling query type3
int l, r;
cin >> l >> r;

l = (l + curr + n) % n;
r = (r + curr + n) % n;

// if l is less than r.
if (l <= r)
cout << (pref[r + 1] - pref[l]) << endl;

// If r is less than l.
else
cout << (pref[n] + pref[r + 1] - pref[l]) << endl;
}
}

return 0;
}``````

Input:

``````n=5, q=4
arr[] = {3, 5, 7, 9, 11}
q1 = {1, 4}
q2 = {3, 0, 3}
q3 = {2, 3}
q4 = {3, 1, 3}``````

Output:

``````Value of n and q are: 5 4
Initial array: 3 5 7 9 11
Sum after query 3: 32
Sum after query 5:15``````

#### 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 are performing queries in constant time i.e., O(1).

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

### Can we change the size of the array at runtime?

The array's size is determined at the time of its creation or initialization. The array's size cannot be changed once it has been created. Even so, if you try to assign a value to a member of the array that is larger than its size, a runtime exception will be thrown.

### How useful is an array in solving programming problems?

An array is a data structure that can hold a fixed number of elements of the same data type in a fixed size. Although an array is used to hold data, it is often more beneficial to conceive of it as a collection of variables of the same type

### What is the major drawback of array data structure?

The most significant constraint of an array is that its size must be defined in advance. Using an array is significant if the Array's maximum size is known ahead of time, and it may result in memory waste. We can use Dynamic Array or Linked List as a solution.

## Conclusion

In this article, we have analyzed queries on the left and right circular shifts on the Array. We have gone through two different approaches to solving the problem based on circular shift, namely brute force, and optimized approach; we have also discussed their algorithm, C++ code, and also their space and time complexity.
After reading about this array problem, are you not feeling excited to read/explore more articles on the topic of array and data structures and algorithms? Don't worry; Coding Ninjas has you covered. To learn more about data structures and algorithms, see Data Structures and AlgorithmsCompetitive Programming. You can also see problems related to arrays at Coding Ninjas Studio.

Check out the following problems -

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Operating SystemUnix File SystemFile System RoutingFile Input/Output.JavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!