Question

You were given a kettle of n birds, which look all the same to you. To decide if two birds are of the same species, you perform the following experiment – you put the two of them in a cage together. If they are friendly to each other, then they are of the same species. Otherwise, you separate them quickly before survival of the fittest kicks in.

1. Suppose that there are exactly p species present in your kettle of n birds. and one species has a plurality: more birds belong to that species than to any other species. Present a procedure to pick out the birds from the plurality species as efficiently as possible (i.e., minimize the number of experiments you have to do as a function of n and p). Do not assume that p = O(1).

Answer 1

This involves the concept of Moore’s Voting algorithm. It is similar to the part in which we have to find the number of species which were occurring more than half of the times. So if you had understood that part just move to the end there i am explaining this part.

This is just for the basic part if we want the species having majority.

the idea behind solving the above-given problem is through Moore’s Voting algorithm.

like, let's say that we have an array of a[] indicating the birds let's assume that the A, C, D belongs to the dominant species.

a[]= A B C D E

So here we keep two possible values and keep their count. these values indicate that they are the ones that are present in the majority in the group. Let's say these are first and second and c1=0,c2=0 are their respective counts.

so initially first='*' and second ='*' and c1=0,c2=0;

now we loop over all the species from i=0 to i=4. (n-1=4)

i=0 : first!='A'. && second !='A' but c1==0 so we make first='A' and c1=1;

i=1: first!='B'. && second !='B' && c1!=0 but c2==0 so we make second='B' and c2=1;

i=2 first!='C'. && second !='B' && c1!=0 but c2!=0 so we make c1--,c2-- both becomes 0. Here assuming that C don't belong to the group of both 'A' & 'B'.

i=3 first=='D' so make c1++; c1=1;

i=4 first=='E' so make c1++; c1=2;

Here first=='X' this means that it is checking if these two belong to the same group or not. See the code given below for more details

so the basic code behind this is given below

bool check( char x, char y){

return (fight(x,y)); // this will call some random function which will tell if thspecies x,y belong to same type or not

}

for (int i = 0; i < n; i++) {

        if (check(first,a[i]))

            count1++;

        else if (check(second,a[i]))

            count2++;

        else if (count1 == 0) {

            count1++;

            first = a[i];

        }

        else if (count2 == 0) {

            count2++;

            second = a[i];

        }

        else {

            count1--;

            count2--;

        }

}

Now we just need to loop one more time over all N species and check the number of counts that the species belong to the first and second. Fo any of these two whichever will have more than half of the species will be that answer;

int cnt1=0,cnt2=0;

for(int i=0;i<n;i++)

{

if(check(a[i],first)  

cnt1++;

else if(check(a[i],second)

cnt2++;

}

if(cnt1>n/2)

cout<<first<<"\n;

else if(cnt2>n/2)

cout<<second <<"\n";

else

cout<<"answer not possible";

So the time complexity for the above code is O(n) where n is size of the array and space complexity is O(1) i.e. constant.

The second part starts from here just like in the previous part where we know that the answer must be possible from either the first or the second value this time instead of just maintaining first and second we maintain p value and their respective counts. So basically above part can be considered as the solution for p=2. for p=1the answer will be the size of array. The idea behind is similar to the previous one . Here is the basic code given below.

struct bird

{

    char ch;

    int c;

};

struct bird temp[p-1];

    for (int i=0; i<p-1; i++)

        temp[i].c = 0;

    for (int i = 0; i < n; i++)

    {

        int j;

        for (j=0; j<p-1; j++)

        {

            if (check(temp[j].ch,arr[i]))//check function is mentioned in the first part

            {

                 temp[j].c += 1;

                 break;

            }

        }

        if (j == p-1)

        {

            int l;

            for (l=0; l<p-1; l++)

            {

                if (temp[l].c == 0)

                {

                    temp[l].ch = arr[i];

                    temp[l].c = 1;

                    break;

                }

            }

            if (l == p-1)

                for (l=0; l<p; l++)

                    temp[l].c -= 1;

        }

    }

int mx=0,pos=0;

    for (int i=0; i<p-1; i++)

    {

        int ac = 0;

        for (int j=0; j<n; j++)

            if (arr[j] == temp[i].e)

                ac++;

        if (ac > mx)

{

mx=ac;

pos=i;

}

    }

cout << "Number:" << temp[pos].ch << " Count:" << mx << endl;

The time complexity for this part will be O(n*p) and space complexity will be O(p) n is the length of the array and p is the plurality.