Hackerrank: Waiter

You are a waiter at a party. There are  stacked plates on pile A0. Each plate has a number written on it. Then there will be Q iterations. In i-th iteration, you start picking up the plates in  Ai-1 from the top one by one and check whether the number written on the plate is divisible by the i-th prime. If the number is divisible, you stack that plate on pile Bi . Otherwise, you stack that plate on pile Ai. After Q iterations, plates can only be on pile B1,B2,..,Bq,Aq. Output numbers on these plates from top to bottom of each piles in order of B1,B2,…,Bq,Aq.

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., A0. The leftmost value represents the bottom plate of the pile.

Constraints

  • 1 <= N <=5 * 10^4
  • 2 <= number_ith <= 10^4
  • 1 <= Q <= 1200

Output Format

Output N lines. Each line contains a number written on the plate. Printing should be done in the order defined above.

Sample Input 0

5 1
3 4 7 6 5

Sample Output 0

4
6
3
7
5

Explanation 0

Initially:

 A0 = [3, 4, 7, 6, 5]<-TOP

After 1 iteration:

 A0 = []<-TOP

 B1 = [6, 4]<-TOP

 A1 = [5, 7, 3]<-TOP

We should output numbers in B1  first from top to bottom, and then output numbers in A1 from top to bottom.

Sample Input 1

5 2
3 3 4 4 9

Sample Output 1

4
4
9
3
3

Explanation 1

Initially:

A0 = [3, 3, 4, 4, 9]<-TOP

After  iteration:

A0 = []<-TOP

B1 = [4, 4]<-TOP

B2 = [9, 3, 3]<-TOP

After  iteration:

A1 = []<-TOP

B1 = [4, 4]<- TOP

B2 = [3, 3, 9]<-TOP

We should output numbers in B1  first from top to bottom, and then output numbers in B2 from top to bottom.


You can tell that the Explanation 1 is wrong but it doesn’t matter. The problem description is quite confusing, but it’s really simple.

You’re given a set and you have to split that set into two separate parts, one that is divisible by some prime numbers, and the other isn’t. The visible part are constructed by multiple stacks. Each iteration i-th, you go through the stack A, if any element in stack A is divisible by i-th prime, put it into a stack B i-th, otherwise put it back in a new stack of A, which will reverse the original stack.

Later on, either when new stack A is empty or we run out of the iteration loop, we go through the stacks B, pop out each element in each stack and print it out. Then go through the final stack A, which might or might not be empty.


This my the solution in Java.

https://github.com/MrNocTV/Algorithms/blob/master/SolvedProblems/HackerRank/src/Waiter.java