Dynamic Array Hackerrank problem solution

                        Dynamic Array Hackerrank

Dynamic Array Hackerrank

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, lastAns, and initialize it to 0.
The 2 types of queries that can be performed on your list of sequences (seqList) are described below:

  • Query: 1 x y
    Find the sequence, seq, at index ((x ⊕ lastAns) % N) in seqList.
    Append integer y to sequence seq.
  • Query: 2 x y
    Find the sequence, seq, at index ((x ⊕ lastAns) % N) in seqList.
    Find the value of element (y%size) in seq (where size is the size of seq) and assign it to lastAns.
    Print the new value of lastAns on a new line

Task
Given N, Q, and Q queries, execute each query.

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

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 Q subsequent lines contains a query in the format defined above.

Constraints

1<=N,Q<=105
0<=x<=109
0<=y<=109
It is guaranteed that query type 2 will never query an empty sequence or index.
Output Format

For each type 2 query, print the updated value of on a new line.

Sample Input

2 5
1 0 5
1 1 7
1 0 3
2 1 0
2 1 1

Sample Output

7
3

Explanation

Initial Values:
N=2
lastAns=0
S0={}
S1={}

Query 0: Append 5 to sequence ((0 ⊕ 0) % 2) =0.
lastAns=0
S0={5}
S1={}

Query 1: Append 7 to sequence ((1 ⊕ 0) % 2) =1.
lastAns=0
S0={5}
S1={7}

Query 2: Append 3 to sequence ((0 ⊕ 0) % 2) =0..
lastAns=0
S0={5,3}
S1={7}

Query 3: Assign the value at index 0 of sequence ((1 ⊕ 0) % 2) =1. to lastAns, print lastAns. lastAns=7

S0={5,3}
S1={7}

7
Query 4: Assign the value at index 1 of sequence ((1 ⊕ 7) % 2) =0 to lastAns, print lastAns. lastAns=3

S0={5,3}
S1={7}

3

Solution
# Enter your code here. Read input from STDIN. Print output to STDOUT

n, m = [int(i)  for i in raw_input().split()] 

#Create the datastructure, It shall be a list of list.
list_of_sequence = []
for i in xrange(n):
    list_of_sequence.append([])
lastans = 0   
for i in xrange(m):
    
    p,q,r = [int(i)  for i in raw_input().split()] 
    if p == 1:
        #Calculate the index.
        index = (q ^ lastans) % n
        list_of_sequence[index].append(r)
    elif p == 2:
        index = index = (q ^ lastans) % n
        element_index = r % len(list_of_sequence[index])
        value = list_of_sequence[index][element_index]
        lastans = value   
        print value
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <limits>
#include <tuple>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>

using namespace std;

vector<int> v[100005];

int main()
{
    int n, q, type, x, y;
    cin>>n>>q;
    assert(n >= 1 && n <= 100000 && q >= 1 && q <= 100000);
    int lastans = 0;
    while(q--)
    {
        cin>>type>>x>>y;
        assert(type >= 1 && type <= 2 && x >= 0 && x <= 1000000000 && y >= 0 && y <= 1000000000);
        if(type == 1)
        {
            v[(lastans^x)%n].push_back(y);
        }
        else
        {
            int pos = (lastans^x)%n;
            int idx = y%((int)v[pos].size());
            lastans = v[pos][idx];
            cout<<lastans<<endl;
        }
    }
    return 0;
}
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int numQueries = scan.nextInt();
        
        // Initialize Empty Sequences
        Vector< Vector<Integer> > seqN = new Vector< Vector<Integer> >(n);
        for(int i = 0; i < n; i++){
            seqN.add(new Vector<Integer>());
        }
        
        // Process Queries
        int lastAns = 0;
        for(int i = 0; i < numQueries; i++){
            int queryType = scan.nextInt();
            int x = scan.nextInt();
            int y = scan.nextInt();
            int seqIndex = ((x ^ lastAns ) % n);
            Vector<Integer> currSeq = seqN.get(seqIndex);
            
            if(queryType == 1){
                currSeq.add(y);
            }
            else{ // Query type 2
                lastAns = currSeq.get(y % currSeq.size());
                System.out.println(lastAns);
            }
        }
        scan.close();
    }
}
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
 
class Solution {
    public static void main(String [] args){
        Scanner input=new Scanner(System.in);
        String l1=input.nextLine();
        String arr1[]=l1.split(" ");
        long N=Long.parseLong(arr1[0]);
        String arr[]=new String[(int)N];
        long lastans=0;
        long Q=Long.parseLong(arr1[1]);
 
        for(long i=0;i<Q;i++){
            String l2=input.nextLine();
            String arr2[]=l2.split(" ");
            int decide=Integer.parseInt(arr2[0]);
            switch(decide){
                case 1:
                    long x=Long.parseLong(arr2[1]);
                    long y=Long.parseLong(arr2[2]);
 
                    long sequence=(x^lastans)%N;
                    arr[(int)sequence]=arr[(int)sequence]+" "+arr2[2];
                    break;
                case 2:
                    long p=Long.parseLong(arr2[1]);
                    long q=Long.parseLong(arr2[2]);
 
                    long sequenc=(p^lastans)%N;
                    String arr3[]=arr[(int)sequenc].split(" ");
                    long index=q%(arr3.length-1);
                    lastans=Long.parseLong(arr3[(int)index+1]);
                    System.out.println(lastans);
                    break;
            }
 
        }
 
    }
}
#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;

    /* input numbers of sequences */
    scanf("%d", &N);
    if (N < 1 || N > MAX_N_Q) {
        return 1;
    }
    /* input numbers of queries */
    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;
}

A web developer(Front end and Back end), and DBA at csdamu.com. Currently working as Salesforce Developer @ Tech Matrix IT Consulting Private Limited. Check me @about.me/s.saifi

Leave a reply:

Your email address will not be published.