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 strictly more than half of the birds belong to the same species. Describe and analyze an efficient algorithm that identifies every bird among the n birds that belong to this dominant species.

Answer 1

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.