brute force technique for the following problem

Question

Given an integer A which denotes the number of people standing in the 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 and return the position of that person in the original queue.

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int A=10,p=0,i;
    vector<bool> mark(A+1,true);
    mark[0]=false;
    for(i=0;i<=A;i=i+2)
    {
        p++;
        if(p==2)
        {
            mark[i]=false;
            p=0;
        }

    }
    for(int j=0;j<A;j++)
    {
      cout<<mark[j];
    }
    for(i=0;i<A;i++)
    {
        if(mark[i]==true)
        {
            cout<<i<<endl;
        }
    }
}

i tried this but it only works for the first set of even numbers ps:i am new here so please forgive me if i asked in a wrong way

Avoid that bits header please. Avoid `using namespace std` globally. — Michael Chourdakis, Jun 14 '20 at 06:49
You only need to round down the length of the queue to the nearest power of two to get the answer (give or take some corner cases). [Here is how to do that.](https://stackoverflow.com/questions/2679815/previous-power-of-2) — G. Sliepen, Jun 14 '20 at 06:56
The reason it only works for the "first set of even numbers" is that you've only implemented the process to extract that first set. Work out a way to put key parts of your code which implements that process into a loop, so the process is repeated. Also, if you have a queue with `A` elements, why are you allocating a vector with `A + 1` elements? — Peter, Jun 14 '20 at 07:03

score 1 · Answer 1 · answered Jun 14 '20 at 07:38

If you are interested in a simple algorithm similar to yours, then please see this example:

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int A = 10, currentSize = A;
    vector<bool> mark(A, true);

    while (currentSize > 1) {
        for (int i = 0, j = 1; i < A; i++) {
            if (mark[i]) {
                if (j % 2 != 0) {
                    mark[i] = false;
                    currentSize--;
                }
                j++;
            }
        }
    }

    for (int i = 0; i < A; i++) {
        if (mark[i]) {
            cout << i + 1 << endl;
            break;
        }
    }

    return 0;
}

If you only need an answer to a problem with a faster algorithm, then I think that this will be correct:

#include <iostream>

using namespace std;

int main()
{
    int A = 10, p = 0;

    while (A / 2 != 0) {
        A /= 2;
        p++;
    }

    cout << pow(2, p);
    return 0;
}

I used VS2017 to compile this code.

brute force technique for the following problem

1 Answers1