Dynamic Array| Array
TASK(easy)
- Declare a 2-dimensional array, arr, of n empty arrays. All arrays are zero indexed.
- Declare an integer, lastAnswer, and initialize it to 0.
- There are 2 types of queries, given as an array of strings for you to parse:
- Query: 1 x y
- Let idx=((x^lastAnswer)%n) .
- Append the integer y to arr[idx].
- Query: 2 x y
- Let idx=((x^lastAnswer)%n) .
- Assign the value arr[idx][y%size(arr[idx])]to lastAnswer.
- Query: 1 x y
3.Store the new value of lastAnswer to an answers array.
Note:^ is the bitwise XOR operation. Finally, size(arr[idx]) is the number of elements in arr[idx]
Function Description
Complete the dynamicArray function below.
dynamicArray has the following parameters:
- int n: the number of empty arrays to initialize in
- string queries[q]: query strings that contain 3 space-separated integers
Returns
- int[]: the results of each type 2 query in the order they are presented
Input Format
The first line contains two space-separated integers,n , the size of arr to create, and q, the number of queries, respectively.
Each of the q subsequent lines contains a query string,queries[i] .
Constraints
1<n, q<105
0<x, y<109
It is guaranteed that query type 2 will never query an empty array or index.
SAMPLE INPUT
2 5
1 0 5
1 1 7
1 0 3
2 1 0
2 1 1
SAMPLE OUTPUT
7
3
SOLUTION 1
def dynamicArray(n, queries):
last_answer = 0
seq = [[] for _ in range(n)]
for q in queries:
op, x, y = q
if op == 1:
seq[(x ^ last_answer) % n].append(y)
elif op == 2:
s = seq[(x ^ last_answer) % n]
last_answer = s[y % len(s)]
print(last_answer)
if __name__ == '__main__':
n, q = map(int, input().split())
queries = []
for _ in range(q):
queries.append(list(map(int, input().split())))
dynamicArray(n, queries)
SOLUTION 2
def dynamicArray(n, queries):
l = [[] for _ in range(n)]
result = []
lastanswer = 0
for i in queries:
a = (lastanswer ^ i[1]) % n
if i[0] == 1:
l[a].append(i[2])
elif i[0] == 2:
a = (lastanswer ^ i[1]) % n
lastanswer = l[a][i[2] % len(l[a])]
result.append(lastanswer)
return result
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
nq = input().rstrip().split()
n = int(nq[0])
q = int(nq[1])
queries = []
for _ in range(q):
queries.append(list(map(int, input().rstrip().split())))
result = dynamicArray(n, queries)
fptr.write('\n'.join(map(str, result)))
fptr.close()
EXPLANATION STEPS
- Initialization: An array A is initialized with zeros based on the given size n.
- Processing Queries:
- Type 1 Query (1 x y): Iterate through the array, updating elements at indices where (i + 1) % x == 0 (to account for 1-based indexing).
- Type 2 Query (2 x): Compute the sum of elements in A that are multiples of x and store the result in the results list.
- Output:The results list contains the results of all type 2 queries, which is printed at the end.
