Algorithm:
Suppose, we have several candidates participating in voting. Now, if the number of candidate is static then it can be done easily in O(n) time complexity with an additional storage for the number of candidates participating in the voting. However, the time required can increased tremendously if
i. The number of voters are not static. In that case, for each vote we have to scan for the candidate and update the count which may cause as worse as O(n*n) time complexity.
ii. We don't have additional space to store the vote. We are allowed to only use O(1) space.
The problem can be solved using Majority Vote Algorithm.
Here, we use two variable to find out the majority. The total comparisons required for this algorithm is 2*n.
There are two variables count and c.
count= total number of vote for the candidate
c= particular candidate
Now, go through the votes one by one in the following fashion
Step 0: Initialize count to be zero
Step 1: Go through the vote
i. Check if the count is zero
if so then assign the c to this vote's candidate and then set count=1
if not then check if this vote's candidate is equal to c
if yes then set count+=1
if no then set count-=1
Step 2: Continue until the end
Step 3: Now, return c
Step 4: Check once again by going through the votes if it is really the majority.
Code:
/*I have used the static number of candidate by defining the array however it works equally fine for dynamic candidate number too. */
#include<stdio.h>
int count_vote(int a[],int size)
{
int count=0,c,i;
for(i=0;i<size;i++)
{
if(count==0)
{
c=a[i];
count=1;
}
else
{
if(c==a[i])
count++;
else
count--;
}
}
return c;
}
int main()
{
int a[]={2,3,2,4,5,2,4,3,2,2,2,8,9,2,7,6,1,2,2,2,4,2,5,6,7,2,1,2,2,2,2};
int size=sizeof(a)/sizeof(a[0]);
int majority,count=0,i;
majority=count_vote(a,size);
for(i=0;i<size;i++)
if(a[i]==majority)
count++;
if(count>size/2)
printf("\nThe %d is a majority with %d vote where total vote is %d .\n",majority,count,size);
else
printf("\nThe %d is not a majority vote but has %d vote in total vote of %d.\n",majority,count,size);
return 0;
}
