Unable to get the logic

#1

please provide a pseudo-code of this question

#2

While this algorithm takes almost same time, it saves a lot of space.
If we look at our algorithm more closely , you will notice that at any point , we only need 3 stacks atmost.

  1. Stack S from which we are popping elements. This is equivalant to stack a[i-1] from the previous method.
  2. Stack A to which we will be pushing the elements in case they are not divisible by ith prime number. This is equivalant to stack a[i] from the previous method.
  3. Stack B to which we will be pushing the elements in case they are divisible by ith prime number. This is equivalant to stack b[i] from the previous method.

After each iteration , make S = A for the next iteration since for the next iteration we will be popping elements out from the stack that is currently A.

After each iteration , we pop and push all elements from B to a queue to maintain the order which would otherwise have been maintained by having different arrays of stack.

This approach requires a lot less space than the previous approach and is thus better.

#3

Naive Algorithm

A simple approach would be to simply make two arrays of stacks and solve as guided. We can precompute the primes using sieve to save time. This approach will take a lot of space as the sizes of arrays will be size = q+1.

#4

I hope ur doubt is cleared now

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.