PROBLEM LINK:
Author: hemanthkumar9
Tester: hemanthkumar9
Editorialist: hemanthkumar9
DIFFICULTY:
EASY
PREREQUISITES:
Properties of Modulo Operation
PROBLEM:
You are given an array A of N integers. You are to fulfill M queries. Each query has one of the following three types:
- L d : Rotate the array A to the left by d units.
- R d : Rotate the array A to the right by d units.
- Q d : Query the element currently at the d-th index in the array, after all earlier rotations have been carried out.
QUICK EXPLANATION:
The problem is to rotate an array in any direction as and when specified. If we rotated the array at each phase, the time complexity of the problem would be O(N^2), which would timeout.
An alternate and more efficient solution is to maintain a record of the offset by which each index has been shifted. For example, if the array was rotated to the right by 3 units, the old index of an element must be added with 3 to get the new index. Likewise, we must subtract to obtain the offset for a left shift.
Thus when an index is requested, we can subtract the offset from it to get the original index. Keep in mind index overflows.
EXPLANATION:
The problem is to rotate an array of size N by some specified amount.
We could do one of three things:
- Rotate the array (O(N) time) using an external array, which would take O(N) extra space
- Rotate the array (O(N) time) in place, which would take O(1) extra space
- Not rotate the array. Instead maintain an offset for the index (O(1)).
We will be discussing the third approach in this editorial.
But first, why are the first two approaches invalid?
We know that rotating an array costs O(N) time. The size of the array, according to the problem statement can be upto 10^5.
We also have M queries, where each query is either a rotation or retrieval.
In the worst case, where M=N and every query is a rotate query, the time complexity is O(M*N) ==> O(N^2).
Now, let’s see the efficient solution
1 2 3 4 5 6 7 8
(rotate right by 3 units)
6 7 8 1 2 3 4 5
Element 1 at index 0, is now at index 3. We observe that 0+3 = 3
Element 7 at index 6 is now at index 1. We observe that (6+3)%8 = 1. (Since 8 is size of array).
Thus adding 3 to the index of every element gives us its new position. We call this value the offset.
A similar logic applies for shifting to the left, where rather than adding to the offset, we subtract from it.
NOTE: This process of adding/subtracting an offset is cumulative. This means, if the array was first shifted right by 6 units, then shifted left by 4 units, the net offset is 6 - 4 = 2.
If, at any point in time, the offset becomes greater than the size of the array, we simply calculate offset = offset % arraySize. Likewise, if the offset becomes less than zero, simply add N to it as it simply rolls over.
Now, when we need index q at any time, we can simply access the element at index q - offset. Since that index has to be added by that offset to get the new index, subtracting the offset from the new index would give our old index.
Note: The actual value of the original index could be index-offset or index-offset-1 depending on your indexing (0-based or 1-based).
Note: When retrieving the index, take care to compute the modulo operation, in case adding the offset caused an index overflow.
SOLUTIONS:
Setter's Solution
n, q = map(int, input().split())
arr = list(map(int, input().split()))
offset = 0
for i in range(q):
query = input().split()
mag = int(query[1])
if query[0] == 'L':
offset -= mag
if offset < 0:
offset += n
elif query[0] == 'R':
offset += mag
else:
print(arr[(mag-offset-1)%n])