Algorithm
Problem Name: Data Structures -
In this HackerRank in Data Structures -
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;
}
#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();
}
}
#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();
}
}
#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();
}
#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()