Waiter| Stack
TASK(medium)
You are a waiter at a party. There is a pile of numbered plates. Create an empty 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 from top to bottom in . 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 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.
A0=[2,3,4,5,6,7]
answers=[]
Begin iterations. On the first iteration, check if items are divisible by 2.
Ai=[7,5,3]
Bi=[6,4,2]
Move B1 elements to answers.
Answers=[2,4,6]
On the second iteration, test if Ai elements are divisible by 3.
A2=[7,5]
B2=[6,4]
Move B2 elements to answers. And on the third iteration, test if elements are divisible by 5.
A3=[7]
B3=[5]
Move B3 to answers. All iterations are complete, so move the remaining elements in , from top to bottom, to .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, and .
The next line contains space separated integers representing the initial pile of plates, i.e., .
Constraints
1<=n<=5*104
2<=number[i]<=104
1<=q<=1200
Sample Input 0
5 1
3 4 7 6 5
Sample Output 0
4
6
3
7
5
SOLUTION 1
def waiter(number, q):
# Write your code here
answer = []
point = 0
index = 2
while point < q:
check = 0
for now in range(1, index + 1):
if index % now == 0:
check += 1
if now < index and check == 2:
break
if check == 2:
point += 1
A = []
B = []
for i in range(len(number)):
if number[i] % index == 0:
A.append(number[i])
else:
B.append(number[i])
if point < q:
B.reverse()
number = B
answer.extend(A)
index += 1
answer.extend(number)
return answer
SOLUTION 2
def waiter(number, q):
# Create the Prime Number List
prime = [2]
num = prime[0]
while len(prime) != q:
num += 1
Prime = True
for i in range(2, num):
if (num % i) == 0:
Prime = False
break
if Prime:
prime.append(num)
answer = []
for j in prime:
# Create two more stacks for storing the output of the operations
B = []
A = []
for _ in range(len(number)):
i = number.pop()
if i % j == 0:
B.append(i)
else:
A.append(i)
while B:
answer.append(B.pop())
number = A
while number:
answer.append(number.pop())
return answer
EXPLANATION STEPS
1. Initializes two stacks (stack_a and stack_b) to store plates and a list (result) to store the final order of plates moved to Stack B.
2. Iterates through each prime number in primes.
3. For each prime, iterates through stack_a, moving plates to stack_b if divisible by the current prime.
4. After processing each prime, moves plates from stack_b to result in reverse order to maintain the correct order of plates.
5. Finally, moves remaining plates from stack_a to result.
