### PROBLEM LINK:

**Author:** Hussain Kara Fallah

**Primary Tester:** Hasan Jaddouh

**Secondary Tester:** Istvan Nagi

**Editorialist:** Udit Sanghi

### DIFFICULTY:

EASY-Medium

### PREREQUISITES:

Queue

### PROBLEM:

Given an array of numbers and m queries. You have the keep doing the following operation -

Divide the take the maximum number and divide it by 2. Now for each query, tell the number we were taking in the Q[i]th operation

### QUICK EXPLANATION:

Take 2 queues, q1 and q2. Push all elements in decreasing order to q1. Now as you are taking the elements see the maximum of q1 and q2, store it and then divide it by 2 and push it in q2. When q1 becomes empty then only look at q2.

### EXPLANATION:

First let’s calculate the constraint on Q[i]. So a[i] < 2^{63}. This means that at most an element will can be divided 63 times before reaching 0. And, there are totally 10^6 items. That means that Q[i] will be at max 63(10^6).

First of all, can u think of a brute-force solution.

Just keep doing all stuff manually like taking the maximum in an array and then dividing it by 2 and putting in the array again. This will take time O(n*6.3*{10^6}).

Now, can we do better.

So taking the max right now takes O(n). We can reduce this to O(log n) by using a priority_queue.

Now the complexity will be This will take time O(logN*6.3*{10^6}).

Hmm… Too slow. We need to do this operation in constant time.

Here’s a key observation -

```
After every number has been once divided, you only need to divide the numbers again in the same order as before. So, currently it doesn't make much sense but it will once you see an example.
Before that, you only need to compare between the highest number which has been divided yet and which has not been divided yet.
n = 5
old_a = [28,25,17,14,13]
new_a = []
// old array contains the element which have not yet been divided yet and new array contains those which have been divided atleast once.
operation 1 - 28
old_a = [25,17,14,13]
new_a = [14]
operation 2 - 25
old_a = [17,14,13]
new_a = [14,12]
operation 3 - 17
old_a = [14,13]
new_a = [14,12,8]
operation 4 - 14
old_a = [13]
new_a = [14,12,8,7]
operation 5 - 14
old_a = [13]
new_a = [12,8,7,7]
operation 6 - 13
old_a = []
new_a = [12,8,7,7,6]
// Now you will realize that we only select [12,8,7,7,6] in order now and keep dividing them.
Like 12,8,7,7,6,12/2,8/2,7/2,7/2,6/2,(12/2)/2,(8/2)/2 etc.
```

For these purposes we can use a queue.

Make 2 queue, q1 and q2.

Push all elements in q1 in decreasing order.

Now for the first operation u’ll choose the maximum element which is the front of q1 and push half of that number in q2.

After that, you’'l have 2 queues to choose from q1,q2, choose the queue which has has the maximum element and keep repeating this until… q1 is empty.

Then, you can just repeat the process with the elements of q2.

Remember to store the answer after each operation. Then, process the queries and answer the queries with the answers you stored.

### EDITORIALIST’s, AUTHOR’S AND TESTER’S SOLUTIONS:

**EDITORIALIST’s solution**: [Here] 333

**AUTHOR’s solution**: [Here] 444

**TESTER’s solution**: [Here] 555