HackerRank Waiter problem solution

In this HackerRank Waiter problem solution, we have to Create an empty answer 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 ith 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 answer. 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.

Problem solution in Python programming.

[n,q] = [int(x) for x in input().split(" ")]
vals = [int(x) for x in input().split(" ")]

#print(n,q,vals)

#http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n
#don't really care about the primes part
def getprimes(n):
    """ Returns  a list of primes < n """
    sieve = [True] * n
    for i in range(3,int(n**0.5)+1,2):
        if sieve[i]:
            sieve[i*i::2*i]=[False]*int(((n-i*i-1)/(2*i)+1))
    return [2] + [i for i in range(3,n,2) if sieve[i]]

bp = [] #badplate (not divis)
gp = [] #goodplate (divis)
tp = [] #tempplate (holder for plate that are not divis)

bp.extend(vals)
primes = getprimes(10000) #magic number to get a little over 1200 primes

p = 0
currentPrime = primes[0]

while (p < q):    
    #print(currentPrime, p)
    while bp:
        cur = bp.pop()
        #print(cur, 'w', cur / currentPrime)
        if (cur % currentPrime == 0):            
            gp.append(cur)
        else:
            tp.append(cur)

    #refresh
    p += 1    
    currentPrime = primes[p]     
    
    #print good plates
    while gp:
        print(gp.pop())
    
    #rework stacks, good plates is already empty from the print above
    bp = tp[:]
    tp[:] = []
    
while bp:
    print(bp.pop()) #print remaining bad plates

Problem solution in Java Programming.

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

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Stack<Integer> all = new Stack<Integer>();
        Stack<Integer> rem = new Stack<Integer>();
        Stack<Integer> divisible = new Stack<Integer>();
        List<Integer> reverse = new ArrayList<Integer>();
        List<Integer> print = new ArrayList<Integer>();
        List<Integer> primes = new ArrayList<Integer>();
        int n = in.nextInt();
        int q = in.nextInt();
        int k = q;
        int i,j=3;
        for(i=0;i<n;i++)
            all.push(in.nextInt());
        primes.add(2);
        boolean div = false;
        while(primes.size() < k){
            div = false;
            for(i=0;i<primes.size() && primes.size() < k;i++){
                if(j%primes.get(i) == 0){
                    div = true;
                    j++;
                    break;
                }
            }
            if(!div){
                primes.add(j);
                j++;
            }
        }
        
        for(i=0;i<primes.size();i++){
            reverse.clear();
            while(!all.empty()){
                if(all.peek() % primes.get(i) == 0){
                    reverse.add(all.pop());
                }
                else{
                    rem.push(all.pop());
                }
            }
            divisible.clear();
            while(!rem.empty())
                divisible.push(rem.pop());
            while(!divisible.empty())
                all.push(divisible.pop());
            Collections.reverse(reverse);
            print.addAll(reverse);
        }
        if(!all.empty()){
            while(!all.empty()){
                print.add(all.pop());
            }
        }
        for(i=0;i<print.size();i++)
            System.out.println(print.get(i));
    }
}

Problem solution in C++ programming.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1300;
const int M = 110000;
int ans[M], stk[M], tmpstk[M],prim[N];
int atop, top, ttop, n,q, num;

void init(){
    num = 0;
    for(int i = 2; i < M; ++ i){
        bool isfind = false;
        for(int j = 2; j <= sqrt(i); ++ j){
            if(i%j==0){
                isfind = true;
                break;
            }
        }
        if(!isfind){
            prim[num ++] = i;
        }
        if(num >= 1200)
            return ;
    }
}

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    scanf("%d%d",&n,&q);
    init();
    atop = top = 0;
    for(int i = 0; i < n; ++ i){
        scanf("%d",&stk[top ++]);
    }
    for(int i = 0; i < q; ++ i){
        ttop = 0;
        while(top){
            int v = stk[top - 1];
            -- top;
            if(v%prim[i] == 0){
                ans[atop ++] = v;
            }else{
                tmpstk[ttop ++] = v;
            }
        }
        while(atop){
            printf("%d\n",ans[atop - 1]);
            -- atop;
        }
        for(int j = 0; j < ttop; ++ j){
            stk[j] = tmpstk[j];
        }
        top = ttop;
        if(!top)
            break;
    }
    while(top){
        printf("%d\n",stk[top - 1]);
        -- top;
    }
    return 0;
}

Problem solution in C programming.

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

#define DSTACK 2
#define OP1    0
#define OP2    1

int sp[3];
int *stack[3];

void initS(int n) {    
    for (int i=0;i<3;++i) {
        stack[i]= (int *) malloc(sizeof(int)*n);
        sp[i]=0;
    } 
}  

void pushS(int i, int v) {
    stack[i][sp[i]++]=v;    
}

int popS(int i) {    
    return stack[i][--sp[i]];
}


void closeS() {
    for (int i=0;i<3;++i) free(stack[i]);
}

int emptyS(int i) {
    return sp[i]==0;
}

int itemsS(int i) {
    return sp[i];
}

int isPrime(int n) {
    
    
    for (int i=2;i*i<=n;++i) {
        if (n%i==0) return 0;
    } 
    
    
    return 1;
    
    
}

int nextPrime(int n) {
    
    ++n;
    
    while(!isPrime(n))
        ++n;
    
    return n;
}



int main() {

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */  
    
    int n, q;
    int i;
    int v;
    int ins, outs, prime;
 
    scanf("%d %d",&n,&q);
    
    int items[q];
    
    initS(n); // init stack
    
    for (i=0;i<n;++i) {
        scanf("%d",&v);
        pushS(0,v); // stack 0
    }
    
    ins=0;
    outs=1;
    prime=2;

    for(i=0;i<q;++i) {
        
        while(!emptyS(ins)) {
            int v= popS(ins);
            if (v%prime==0) pushS(DSTACK,v); //stack2 
            else pushS(outs,v); 
        }    
        
        items[i]=itemsS(DSTACK);
        
        // SWAP stacks
        int tmp=ins;
        ins=outs;
        outs=tmp;
        
        prime=nextPrime(prime);
        
        while(!emptyS(DSTACK)) {
            v= popS(DSTACK);
            printf("%d\n",v);
        } 
    }
    
    while(!emptyS(ins)) {
        v= popS(ins);
        printf("%d\n",v);
    }
    
    closeS();
    
    return 0;
}

Problem solution in JavaScript programming.

process.stdin.resume();
process.stdin.setEncoding('ascii');

var input_stdin = "";
var input_stdin_array = "";
var input_currentline = 0;

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

process.stdin.on('end', function () {
    input_stdin_array = input_stdin.split("\n");
    main();    
});

function readLine() {
    return input_stdin_array[input_currentline++];
}

/////////////// ignore above this line ////////////////////

function main() {
    var n_temp = readLine().split(' ');
    var n = parseInt(n_temp[0]);
    var q = parseInt(n_temp[1]);
    number = readLine().split(' ');
    number = number.map(Number);
       
    var aStacks = [number]
    var bStacks = [[]]
    var primes = getNPrimes(q)
    
    for (var i = 1; i <= q; i++){
        bStacks.push([])
        aStacks.push([])
        while (aStacks[i-1].length > 0){
            var item = aStacks[i-1].pop()
            if (item % primes[i-1] == 0) {
                bStacks[i].push(item)
            }
            else aStacks[i].push(item)
        }
    }
   
    for (i in bStacks){
        printStack(bStacks[i])
    }
    
    for (i in aStacks){
        printStack(aStacks[i])
    }

}

function printStack(stack){
    while (stack.length > 0) console.log(stack.pop())
}

function getNPrimes(n){
    var primes = []
    var i = 2
    
    while (primes.length < n){
        if (isPrime(i)) primes.push(i)
        i++
    }
    
    return primes
}


function isPrime(n){
    for (var i = 2; i < n; i++){
        if (n%i == 0) return false
    }
    return true
}