## Algorithm

Problem Name: Data Structures - Waiter

In this HackerRank in Data Structures - Waiter solutions

You are a waiter at a party. There is a pile of numbered plates. Create an empty answers array. At each iteration, i remove each plate from the top of the stack in order. Determine if the number on the plate is evenly divisible by the i**th prime number. If it is, stack it in pile Bi. Otherwise, stack it in stack Ai , Store the values in Bi from top to bottom in answers. In the next iteration, do the same with the values in stack Ai. Once the required number of iterations is complete, store the remaining values in Ai in answers again from top to bottom. Return the answers array.

Example

A = [2,3,4,5,6,7]

q = 3

An abbreviated list of primes is [2,3,5,7,11,13]. Stack the plates in reverse order.

Ao = [2,3,4,5,6,7]

answers = []

Begin iterations. On the first iteration, check if items are divisible by 2.

A1 = [7,5,3]

B1 = [6,4,2]

Move B1 elements to answers.

answers = [2,4,6]

On the second iteration, test if A1 elements are divisible by 3.

A1 = [7,5]

B2 = [3]

Move B2 elmements to answers.

answers = [2,4,6,3]

And on the third iteration, test if A2 elements are divisible by 5.

A3  = [7]

B3 = [5]

Move B2 elmements to answers.

answers = [2,4,6,3,5]

All iterations are complete, so move the remaining elements in A3, from top to bottom, to answers.

answers = [2,4,6,3,5,7]. Return this list.

Function Description

Complete the waiter function in the editor below.

waiter has the following parameters:

• int number[n]: the numbers on the plates
• int q: the number of iterations

Returns

• int[n]: the numbers on the plates after processing

Input Format

The first line contains two space separated integers n and q.

The next line contains n space separated integers representing the initial pile of plates, i.e., A.

Constraints

1 <= n <= 5 * 10**6

2 <= number[i] <= 10**4

1 <=q <= 1200

Sample Input 0

```5 1
3 4 7 6 5
```

Sample Output 0

```4
6
3
7
5
```

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
#include <bits/stdc++.h>

using namespace std;

string ltrim(const string &);
string rtrim(const string &);
vector < string> split(const string &);

/*
* Complete the 'waiter' function below.
*
* The function is expected to return an INTEGER_ARRAY.
* The function accepts following parameters:
*  1. INTEGER_ARRAY number
*  2. INTEGER q
*/

vector<int> waiter(vector<int> number, int q) {
vector<int> result;
vector<int> prime;
prime.push_back(2);
int n=3;
while(q>1)
{
int flag=0;
for(int i=2;i*i < =n;i++)
{
if(n%i==0){flag=1;break;}
}
if(flag==0){prime.push_back(n);q--;}
n++;
}
reverse(prime.begin(),prime.end());
//reverse(number.begin(),number.end());
int x=prime.size();
x--;
while(x>=0)
{
int p=prime[x];
cout<<p<<" ";
for(auto it=number.begin();it!=number.end();it++)
{
if(*it%p==0)
{
result.push_back(*it);
number.erase(it);
it--;
}
}
reverse(number.begin(),number.end());
x--;
}
reverse(number.begin(),number.end());
for(auto it=number.begin();it!=number.end();it++)
{
result.push_back(*it);
}
return result;
}

int main()
{
ofstream fout(getenv("OUTPUT_PATH"));

string first_multiple_input_temp;
getline(cin, first_multiple_input_temp);

vector < string> first_multiple_input = split(rtrim(first_multiple_input_temp));

int n = stoi(first_multiple_input[0]);

int q = stoi(first_multiple_input[1]);

string number_temp_temp;
getline(cin, number_temp_temp);

vector < string> number_temp = split(rtrim(number_temp_temp));

vector<int> number(n);

for (int i = 0; i  <  n; i++) {
int number_item = stoi(number_temp[i]);

number[i] = number_item;
}

vector<int> result = waiter(number, q);

for (size_t i = 0; i  <  result.size(); i++) {
fout << result[i];

if (i != result.size() - 1) {
fout << "\n";
}
}

fout << "\n";

fout.close();

return 0;
}

string ltrim(const string &str) {
string s(str);

s.erase(
s.begin(),
find_if(s.begin(), s.end(), not1(ptr_fun < int, int>(isspace)))
);

return s;
}

string rtrim(const string &str) {
string s(str);

s.erase(
find_if(s.rbegin(), s.rend(), not1(ptr_fun < int, int>(isspace))).base(),
s.end()
);

return s;
}

vector < string> split(const string &str) {
vector<string> tokens;

string::size_type start = 0;
string::size_type end = 0;

while ((end = str.find(" ", start)) != string::npos) {
tokens.push_back(str.substr(start, end - start));

start = end + 1;
}

tokens.push_back(str.substr(start));

return tokens;
}
``````
Copy The Code &

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

/*
* Complete the 'waiter' function below.
*
* The function is expected to return an INTEGER_ARRAY.
* The function accepts following parameters:
*  1. INTEGER_ARRAY number
*  2. INTEGER q
*/

public static List < Integer> waiter(List number, int q) {
List primes = getPrimes(q), answers = new ArrayList();
Stack a = new Stack(), b = new Stack();
for (int i = 0; i  <  q; i++) {
for(int j = number.size() - 1; j > -1; j--) {
if(number.get(j) % primes.get(i) == 0)
b.push(number.get(j));
else
a.push(number.get(j));
}
number.clear();
number.addAll(a);
a.clear();
while(!b.isEmpty())
answers.add(b.pop());
}

while(!number.isEmpty())
answers.add(number.remove(number.size()-1));
return answers;

}
static List < Integer> getPrimes(int q) {
List primes = new ArrayList();
for(int c = 0; c  <  q; c++){
for (int i = 2; ; i++) {
boolean flag = true;
for(int j = 2; j  < = Math.sqrt(i); j++) {
if(i % j == 0) {
flag = false;
break;
}
}
if(flag) {
primes.add(i);
c++;
if(c >= q)
break;
}
}
}
return primes;
}

}

public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\\s+\$", "").split(" ");

int n = Integer.parseInt(firstMultipleInput[0]);

int q = Integer.parseInt(firstMultipleInput[1]);

List < Integer> number = Stream.of(bufferedReader.readLine().replaceAll("\\s+\$", "").split(" "))
.map(Integer::parseInt)
.collect(toList());

List result = Result.waiter(number, q);

bufferedWriter.write(
result.stream()
.map(Object::toString)
.collect(joining("\n"))
+ "\n"
);

bufferedReader.close();
bufferedWriter.close();
}
}
``````
Copy The Code &

### #3 Code Example with C# Programming

```Code - C# Programming```

``````
using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;

class Result
{

/*
* Complete the 'waiter' function below.
*
* The function is expected to return an INTEGER_ARRAY.
* The function accepts following parameters:
*  1. INTEGER_ARRAY number
*  2. INTEGER q
*/

public static List < int> waiter(List<int> number, int q)
{
List<int> primelist = new List<int>();
Stack<int> stacklistesi = new Stack<int>();
for (int y = 0; y  <  number.Count; y++)
{
stacklistesi.Push(number[y]);
}
var result = new List < int>();
primelist.Add(2);
q--;
int i = 3;
while (q > 0)
{
if (isPrime(i))
{
primelist.Add(i);
q--;
}
i += 2;
}
var n = 0;
Stack < int> stack = new Stack<int>();
Stack<int> stack2 = new Stack<int>();
while (n  <  primelist.Count)
{

if (stacklistesi.Count > 0)
{
if (stacklistesi.Peek() % primelist[n] == 0)
{
stack.Push(stacklistesi.Pop());
}
else
{
stack2.Push(stacklistesi.Pop());
}

}
else
{
var stack3 = new Stack < int>();
while (stack.Count > 0)
{
result.Add(stack.Pop());
}
while (stack2.Count > 0)
{

stack3.Push(stack2.Pop());

}
while (stack3.Count > 0)
{
stacklistesi.Push(stack3.Pop());
}

n++;
}

}
while (stacklistesi.Count > 0)
{
result.Add(stacklistesi.Pop());
}
return result;
}
public static bool isPrime(long n)
{
if (n == 1)
return false;
if (n == 2) return true;
for (int i = 2; i  < = Math.Sqrt(n); i++)
{
if (n % i == 0)
{
return false;

}
}
return true;
}

}

class Solution
{
public static void Main(string[] args)
{
TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

string[] firstMultipleInput = Console.ReadLine().TrimEnd().Split(' ');

int n = Convert.ToInt32(firstMultipleInput[0]);

int q = Convert.ToInt32(firstMultipleInput[1]);

List < int> number = Console.ReadLine().TrimEnd().Split(' ').ToList().Select(numberTemp => Convert.ToInt32(numberTemp)).ToList();

List<int> result = Result.waiter(number, q);

textWriter.WriteLine(String.Join("\n", result));

textWriter.Flush();
textWriter.Close();
}
}
``````
Copy The Code &

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', function(inputStdin) {
inputString += inputStdin;
});

process.stdin.on('end', function() {
inputString = inputString.split('\n');

main();
});

function readLine() {
return inputString[currentLine++];
}

/*
* Complete the 'waiter' function below.
*
* The function is expected to return an INTEGER_ARRAY.
* The function accepts following parameters:
*  1. INTEGER_ARRAY number
*  2. INTEGER q
*/

function waiter(number, q) {
// Find n-th prime number
// Usually it's done recursively, but since the query is incremental 1, 2, ... q
// We'll just store the previous prime numbers in primes[], and find the next prime number
const primes = [2, 3];
function getPrime(n) {
let m = primes[primes.length-1];
while(primes.length  < = n) {
m += 2;
let isPrime = true;
for (let i = 0; primes[i]  < = Math.sqrt(m); i++) {
isPrime &= m % primes[i] > 0
if (!isPrime) break;
}
if (isPrime) primes.push(m);
}
return primes[n];
}

// Finding answers here
const answers = [];
for (let i = 0; i  <  q; i++) {
//when i-th query is odd, check from number index 0 to n-1
//when i-th query is even check from number index n-1 to 0
let j = i % 2 ? number.length - 1 : 0;
while(i % 2 && j>=0 || !(i % 2) && j  <  number.length) {
if (number[j] % getPrime(i) === 0) {
answers.push(number[j]);
//remove the number that is moved to answers
number.splice(j, 1);
} else {
j += i % 2 ? -1 : 1;
}
}
}

// concat the rest of number
// if number of query is odd, add from number index 0 to n-1
if (q % 2) return answers.concat(number);

// if number of query is even add from number index 0 to n-1
for (let i = number.length - 1; i >= 0; i--) answers.push(number[i]);
return answers;
}

function main() {
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

const firstMultipleInput = readLine().replace(/\s+\$/g, '').split(' ');

const n = parseInt(firstMultipleInput[0], 10);

const q = parseInt(firstMultipleInput[1], 10);

const number = readLine().replace(/\s+\$/g, '').split(' ').map(numberTemp => parseInt(numberTemp, 10));

const result = waiter(number, q);

ws.write(result.join('\n') + '\n');

ws.end();
}
``````
Copy The Code &

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'waiter' function below.
#
# The function is expected to return an INTEGER_ARRAY.
# The function accepts following parameters:
#  1. INTEGER_ARRAY number
#  2. INTEGER q
#

def waiter(number, q):
lower = 2
upper = 10000
p = [i for i in range(lower, upper + 1) if all(i % j != 0 for j in range(2, i))]

ans = []
stackA = []
stackB = []

for i in range(q):
if i == 0:
s = number
else:
s = stackA
stackA = []

for j in range(len(s)):
x = s.pop()
if x % p[i] == 0:
stackB.append(x)
else:
stackA.append(x)
while stackB:
ans.append(stackB.pop())

while stackA:
ans.append(stackA.pop())
return ans

if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')

first_multiple_input = input().rstrip().split()

n = int(first_multiple_input[0])

q = int(first_multiple_input[1])

number = list(map(int, input().rstrip().split()))

result = waiter(number, q)

fptr.write('\n'.join(map(str, result)))
fptr.write('\n')

fptr.close()
``````
Copy The Code &
Advertisements