Dynamic Array


Problem Statement :


Create a list, seqList, of n empty sequences, where each sequence is indexed from 0 to n-1. The elements within each of the n sequences also use 0-indexing.
Create an integer, lastAnswer, and initialize it to 0.
There are 2 types of queries that can be performed on the list of sequences:
    1. Query: 1 x y
          a. Find the sequence, seq, at index ((x xor lastAnswer)%n) in seqList.
          b. Append integer y to sequence seq.
    2. Query: 2 x y
         a. Find the sequence, seq, at index ((x xor lastAnswer)%n) in seqList.
         b. Find the value of element y%size in seq (where size is the size of seq) and assign it to 
              lastAnswer.
         c. Print the new value of lastAnswer on a new line

Note: xor is the bitwise XOR operation, which corresponds to the ^ operator in most languages. Learn more about it on Wikipedia.  is the modulo operator.


Function Description:

Complete the dynamicArray function below.

dynamicArray has the following parameters:
- int n: the number of empty sequences to initialize in seqList.
- string queries[q]: an array of query strings

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 number of sequences) and q (the number of queries), respectively.
Each of the  subsequent lines contains a query in the format defined above, queries[i].


Constraints:
    1. 1<=n,q<=10^5
    2. 0<=x<=10^9
    3. 0<=y<=10^9
    4. It is guaranteed that query type  will never query an empty sequence or index.



Solution :


                        In C:

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

#define MAX_N_Q 100000

#define MAX_X_Y 1000000000

typedef struct linklist {
    int data;
    struct linklist *next;
}linknode, *linklistp;

typedef struct {
    linklistp head;
    int size;
}SEQUENCE;

linklistp insert_tail(linklistp head,linklistp newnode)
{

    if (head == NULL) {
        head = newnode;
    } else {
        linklistp temp = head;
        while(temp->next != NULL)
            temp = temp->next;

        newnode->next = NULL;
        temp->next = newnode;
    }

    return head;
}

void outputlinklist(linklistp head) {
	linklistp temp = head;
    while(temp)	{
        printf("%d",temp->data);
        temp = temp->next;
        if (temp!=NULL)
            printf("\n");
    }
}

int main()
{
    int N, Q;
    int i = 0;
    int choice, x, y, index;
    int lastans = 0;
    SEQUENCE *s = NULL;
    linklistp node, temp, output = NULL, outnode;

    scanf("%d", &N);
    if (N < 1 || N > MAX_N_Q) {
        return 1;
    }
    scanf("%d", &Q);
    if (Q < 1 || Q > MAX_N_Q) {
        return 1;
    }

    s = malloc(sizeof(SEQUENCE)*N);
    if(s == NULL) {
        return 1;
    }

    memset(s, 0, sizeof(SEQUENCE)*N);

    do {
        scanf("%d", &choice);
        scanf("%d", &x);
        scanf("%d", &y);

        if (choice != 1 && choice != 2) {
            return 1;
        }

        if (x < 0 || x > MAX_X_Y) {
            return 1;
        }

        if (y < 0 || y > MAX_X_Y) {
            return 1;
        }

        switch(choice){
            case 1:
                index = (x^lastans)%N;
                node = malloc(sizeof(linknode));
                if (node == NULL)
                    return 1;
                node->data = y;
                node->next = NULL;

                s[index].size ++;
                s[index].head = insert_tail(s[index].head, node);
                break;

            case 2:
                index = (x^lastans)%N;
                y = y % (s[index].size);
                temp = s[index].head;

                while ( y > 0) {
                    temp = temp->next;
                    y--;
                }

                lastans = temp->data;
                outnode = malloc(sizeof(linknode));
                outnode ->data = temp->data;
                output = insert_tail(output, outnode);
                break;

        }

        i++;

    }while (i < Q);

    if (output != NULL)
        outputlinklist(output);

    return 0;
}







In C++:

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main()
{
	int n, q;
	int lastans = 0;
	cin >> n >> q;
	vector<vector<int>>sqces(n);
	while (q--)
	{
		int a;
		long long x, y;
		cin >> a >> x >> y;
		long long t = (x^lastans) % n;
		if (a == 1)
		{
			sqces[t].push_back(y);
		}
		else
		{
			long long size = sqces[t].size();
			long long b;
			if (size != 0)
				b = y%size;
			else
				continue;
			cout << sqces[t][b] << endl;
			lastans =sqces[t][b];
		}
	}
	return 0;
}







In Java:

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int q = in.nextInt();
        List<Integer>[] sequences = new List[n];
        for (int n_i = 0; n_i < n; n_i++) {
            sequences[n_i] = new ArrayList<>();
        }
        int lastans = 0;
        for (int i = 0; i < q; i++) {
            int t = in.nextInt();
            int x = in.nextInt();
            int y = in.nextInt();
            List<Integer> sequence = sequences[(x^lastans)%n];
            switch (t) {
                case 1:
                    sequence.add(y);
                    break;
                case 2:
                    lastans = sequence.get(y%sequence.size());
                    System.out.println(lastans);
                    break;
            }
        }
    }
}







In Python 3:

n, q = map(int, input().split())
l = [[] for _ in range(n)]

latsans = 0
for _ in range(q):
    a, x, y = map(int, input().split())
    if a == 1:
        l[(x^latsans)%n].append(y)
    else:
        t = (x^latsans)%n
        latsans = l[t][y%len(l[t])]
        print(latsans)
    #print(a, x, y, l)