Algorithm


Problem Name: Data Structures - Dynamic Array

Problem Link: https://www.hackerrank.com/challenges/dynamic-array/problem?isFullScreen=true

In this HackerRank in Data Structures - Dynamic Array

  • Declare a 2-dimensional array, arr, of n empty arrays. All arrays are zero indexed.
  • Declare an integer, lastAnswer, and initialize it to 0.
  • Declare an answers array.
  • Parse through each query. The format of each query will be [type, x, y]. There are 2 types of queries, given as an array of strings for you to parse, treat them according to their type:
    1. Query: 1 x y
      1. Let idx = ( (x ^ lastAnswer) % n ).
      2. Append the integer y to arr[idx].
    2. Query: 2 x y
      1. Let idx = ( (x ^ lastAnswer) % n ).
      2. Assign the value arr[idx][y % size(arr[idx])] to lastAnswer.
      3. Store the new value of lastAnswer to answers array.
  • Return answers array.

Note: ^ is the bitwise XOR operation. % is the modulo operator.
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 arr

 - 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, quires[i]

 

Constraints

  • 1 <= n,q <= 10**5
  • 0 <= x <= 10**9
  • 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

 

 

 

 

Code Examples

#1 Code Example with C Programming

Code - C Programming


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

typedef struct Seq_ {
  int *dat;
  int sz;
} Seq;

Seq seq[100001];

void insert(int n, int y) {
  seq[n].dat = realloc(seq[n].dat, seq[n].sz += 1);
  seq[n].dat[seq[n].sz-1] = y;
}

int print(int n, int y) {
  int t = seq[n].dat[y % seq[n].sz];
  printf("%d\n", t);
  return t;
}

int main() {
  FILE *f = stdin;

  int n, q;
  fscanf(f, "%d %d", &n, &q);
  int lastans = 0;
  for (int i = 0; i  <  q; i++) {
    int op, x, y;
    fscanf(f, "%d %d %d", &op, &x, &y);
    int seq = (x ^ lastans) % n;
    if (op == 1)
      insert(seq, y);
    else // op == 2
      lastans = print(seq, y);
  }

  return 0;
}
Copy The Code & Try With Live Editor

#2 Code Example with C++ Programming

Code - C++ Programming


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


int main() {
    int N = 0, Q = 0;
    int lastans = 0;
    int type, x, y;
    int seq = 0;
    int pos;
    
    cin >> N >> Q;
    
    vector  <  vector <int>> a(N);
    
    for (int i = 0; i  <  Q; i ++) {
        cin >> type >> x >> y;
        seq = ((x ^ lastans) % N);
       // cout << seq << endl;
        if (type == 1) {
            a[seq].push_back(y);
           // cout << (seq) << "  < -- " << y << endl;
        }
        else if (type == 2) {
            pos = (y % a[seq].size());
            //cout << "pos " << pos << endl;
            lastans = a[seq][pos];
            cout << lastans << endl;
        }
        
    }
    return 0;
}
Copy The Code & Try With Live Editor

#3 Code Example with Java Programming

Code - Java Programming


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

public class Solution {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		ArrayList < ArrayList());
        }
		int q = sc.nextInt();
		int lastans = 0;
		for (int i = 0; i  <  q; i++) {
			if (sc.nextInt() == 1) {
				lists.get((sc.nextInt() ^ lastans) % n).add(sc.nextInt());
			}
			else {
				ArrayList < Integer> l = lists.get((sc.nextInt() ^ lastans) % n);
				lastans = l.get(sc.nextInt() % l.size());
				System.out.println(lastans);
			}
		}
    }
}
Copy The Code & Try With Live Editor

#6 Code Example with C# Programming

Code - C# Programming


using System;
using System.Collections.Generic;

class Solution
{
    static void Main(string[] args)
    {
        List < int> seq;
        var userInput = Console.ReadLine();
        var userInputSplits = userInput.Split(' ');
        var numberOfSequences = int.Parse(userInputSplits[0]);
        var numberOfQueries = int.Parse(userInputSplits[1]);
        var seqList = new List < List<int>>(new List < int>[numberOfSequences]);
        var lastAns = 0;
        for (var i = 0; i  <  numberOfQueries; i++)
        {
            userInput = Console.ReadLine();
            userInputSplits = userInput.Split(' ');
            var queryType = int.Parse(userInputSplits[0]);
            var x = int.Parse(userInputSplits[1]);
            var y = int.Parse(userInputSplits[2]);
            var seqIndex = (x ^ lastAns) % numberOfSequences;
            switch (queryType)
            {
                case 1:
                    if (seqList[seqIndex] != null)
                        seqList[seqIndex].Add(y);
                    else
                    {
                        seq = new List < int>();
                        seq.Add(y);
                        seqList[seqIndex] = seq;
                    }
                    break;
                case 2:
                    seq = seqList[seqIndex];
                    lastAns = seq[y % seq.Count];
                    Console.WriteLine(lastAns);
                    break;
            }
        }
    }
}
Copy The Code & Try With Live Editor

#4 Code Example with Javascript Programming

Code - Javascript Programming


function processData(input) {
    //Enter your code here
    var lines = input.split('\n');
    var NQ = lines[0].split(' ').map(Number);
    var N = NQ[0];
    var Q = NQ[1];
    var lastans = 0;
    var sequences = [];
    for (var i = 0; i  < = N; i++) {
        sequences[i] = [];
    }
    lines.slice(1).forEach(function (line) {
        var query = line.split(' ').map(Number);
        var x = query[1];
        var y = query[2];
        if (query[0] === 1) {
            var sequenceNum = (x ^ lastans) % N;
            sequences[sequenceNum].push(y);
        } else if (query[0] === 2) {
            var sequenceNum = (x ^ lastans) % N;
            var size = sequences[sequenceNum].length;
            var element = sequences[sequenceNum][y % size];
            console.log(element);
            lastans = element;
        }
    });
} 

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});
Copy The Code & Try With Live Editor

#5 Code Example with Python Programming

Code - Python Programming


a = input().split(' ')
N, Q = [int(e) for e  in a]
arrays = [[] for _ in range(N)]
lastans = 0

def insert(x, y):
    global lastans
    arrays[(x ^ lastans) % N].append(y)
def printnum(x, y):
    global lastans
    inst = arrays[(x ^ lastans) % N]
    lastans = inst[y % len(inst)]
    print(lastans)
    
    
for i in range(Q):
    line = [int(e) for e in input().split(' ')]
    insert(line[1], line[2]) if line[0] == 1 else printnum(line[1], line[2])
Copy The Code & Try With Live Editor

#7 Code Example with PHP Programming

Code - PHP Programming



Copy The Code & Try With Live Editor
Advertisements

Demonstration


Previous
[Solved] 2D Array - DS solution in Hackerrank - Hacerrank solution C,C++, C#, java,js, Python
Next
[Solved] Left Rotation solution in Hackerrank - Hacerrank solution C,C++, C#, java,js, PHP, Python