Selecting alternate positions n a queue

Question

Some people are standing in a queue. A selection process follows a rule where people standing on even positions are selected. Of the selected people a queue is formed and again out of these only people on even position are selected. This continues until we are left with one person. Find out the position of that person in the original queue.

How can I modify the code so that it works when queue has odd no of elements in it because at some point(in the while loop),queue will certainly have odd no of elements.

int main() 
{
    int temp=0,x,n,i;
    cin>>x;
    while(x--) {
        cin>>n;

        queue<int> q;
        for(i=1;i<=n;i++)
            q.push(i);
        while(q.size()!=1) {
            q.pop();
            temp=q.front();
            q.pop();
            q.push(temp);
        }
        cout<<temp;
    }
    return 0;
}

input:5 Expected ouput:4

Time to [learn how to debug your programs](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/). And stop going to inline judge or competition sites to learn programming, that won't teach you to become a good programmer. [Get a few good books](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list/388282#388282) or go to class. — Some programmer dude, Mar 24 '19 at 05:25
@Someprogrammerdude I am not convinced that debugging will help here. If the code does work and just is known not to work on odd lengths, then debugging the working code will only show the known behaviour. — Yunnosch, Mar 24 '19 at 05:30
How about treating an odd-sized queue as an even-sized one with on fewer element, then handle the remaining (or maybe the first) one specially? — Yunnosch, Mar 24 '19 at 05:31
@Yunnosch No that won't work since in every alternate iterartion the size of queue will be odd.If it would have been that size of queue always remains even in all iterations (and odd only in the starting),then your solution would have worked. — mania, Mar 24 '19 at 11:51

score 1 · Accepted Answer · answered Mar 24 '19 at 18:38

The key is in the problem statement: Of the selected people a queue is formed. When you select people from q, don't put them back in the same queue, put them in a new one. Once you're done with that selection, swap the two queues (to replace the old queue with the new queue) before moving on to the next iteration.

score 0 · Answer 2 · answered Mar 24 '19 at 19:59

The basic problem appears to be that you are putting the selected positions at the end of your queue, appending your new queue to your old one. This would work if the start of the new queue corresponded to the start of an iteration of your while loop. However, this does not work when the old queue has an odd length.

The next step for your approach would be to drop the last element from the old queue if the length is odd. That gives you an even-length queue that works. The new problem is figuring out when you've found the start of the new queue so you can repeat the process (of checking for an odd length).

One way to do this would be to put a sentinel value at the beginning of your queue. So when building your initial queue, build it with the numbers 0 through n instead of just 1 through n. The first thing your loop would do is check to see if the front of the queue is zero. If it is, pop it, force the remaining queue to have an even length, then push zero on the end. After that, proceed as you have it (pop, pop, push).

A less cryptic approach would be to use two queues instead of simulating two queues.

A faster approach would be to remove the loop and use a formula. (Which formula? It's a reasonable math exercise, so I'll leave it to you to figure out. Especially since the original problem is also an exercise. I'll just mention that the math involves powers of 2.)

Selecting alternate positions n a queue

2 Answers2