#include<stdio.h>
// function to find the majority candidate in a array arr
int findMajorityCandidate(int arr[], int size)
{
// maj_index - to keep a track of majority candidate
int maj_index = 0, count = 1;
int i;
for(i = 1; i < size; i++)
{
// if the element is same as majority candidate
// increment count
if(arr[maj_index] == arr[i])
{
count++;
}
// else, decrease count
else
{
count--;
}
// at any time if count becomes 0
if(count == 0)
{
// change the majority cadidate
maj_index = i;
count = 1;
}
}
// return the majority candidate
return arr[maj_index];
}
// a function to print the majority element
void printMajorityElement(int arr[], int size)
{
// find the majority element
int candidate = findMajorityCandidate(arr,size);
int i, count = 0;
// count the number of occurrences
for (i = 0; i < size; i++)
{
if(arr[i] == candidate)
count++;
}
if (count > size/2)
printf("Majority element = %d",candidate
); else
printf("No majority element found"); }
int main(void)
{
int arr[] = {2,2,2,3,4,5,6,7};
printMajorityElement(arr, 8);
return 0;
}
I2luY2x1ZGU8c3RkaW8uaD4KIAovLyBmdW5jdGlvbiB0byBmaW5kIHRoZSBtYWpvcml0eSBjYW5kaWRhdGUgaW4gYSBhcnJheSBhcnIKaW50IGZpbmRNYWpvcml0eUNhbmRpZGF0ZShpbnQgYXJyW10sIGludCBzaXplKQp7CiAgICAvLyBtYWpfaW5kZXggLSB0byBrZWVwIGEgdHJhY2sgb2YgbWFqb3JpdHkgY2FuZGlkYXRlCiAgICBpbnQgbWFqX2luZGV4ID0gMCwgY291bnQgPSAxOwogICAgaW50IGk7CiAKICAgIGZvcihpID0gMTsgaSA8IHNpemU7IGkrKykKICAgIHsKICAgICAgICAvLyBpZiB0aGUgZWxlbWVudCBpcyBzYW1lIGFzIG1ham9yaXR5IGNhbmRpZGF0ZQogICAgICAgIC8vIGluY3JlbWVudCBjb3VudAogICAgICAgIGlmKGFyclttYWpfaW5kZXhdID09IGFycltpXSkKICAgICAgICB7CiAgICAgICAgICAgIGNvdW50Kys7CiAgICAgICAgfQogICAgICAgIC8vIGVsc2UsIGRlY3JlYXNlIGNvdW50CiAgICAgICAgZWxzZQogICAgICAgIHsKICAgICAgICAgICAgY291bnQtLTsKICAgICAgICB9CiAKICAgICAgICAvLyBhdCBhbnkgdGltZSBpZiBjb3VudCBiZWNvbWVzIDAKICAgICAgICBpZihjb3VudCA9PSAwKQogICAgICAgIHsKICAgICAgICAgICAgLy8gY2hhbmdlIHRoZSBtYWpvcml0eSBjYWRpZGF0ZQogICAgICAgICAgICBtYWpfaW5kZXggPSBpOwogICAgICAgICAgICBjb3VudCA9IDE7CiAgICAgICAgfQogICAgfQogCiAgICAvLyByZXR1cm4gdGhlIG1ham9yaXR5IGNhbmRpZGF0ZQogICAgcmV0dXJuIGFyclttYWpfaW5kZXhdOwp9CiAKLy8gYSBmdW5jdGlvbiB0byBwcmludCB0aGUgbWFqb3JpdHkgZWxlbWVudAp2b2lkIHByaW50TWFqb3JpdHlFbGVtZW50KGludCBhcnJbXSwgaW50IHNpemUpCnsKICAgIC8vIGZpbmQgdGhlIG1ham9yaXR5IGVsZW1lbnQKICAgIGludCBjYW5kaWRhdGUgPSBmaW5kTWFqb3JpdHlDYW5kaWRhdGUoYXJyLHNpemUpOwogCiAgICBpbnQgaSwgY291bnQgPSAwOwogCiAgICAvLyBjb3VudCB0aGUgbnVtYmVyIG9mIG9jY3VycmVuY2VzCiAgICBmb3IgKGkgPSAwOyBpIDwgc2l6ZTsgaSsrKQogICAgewogICAgICAgIGlmKGFycltpXSA9PSBjYW5kaWRhdGUpCiAgICAgICAgICAgIGNvdW50Kys7CiAgICB9CiAgICBpZiAoY291bnQgPiBzaXplLzIpCiAgICAgICAgcHJpbnRmKCJNYWpvcml0eSBlbGVtZW50ID0gJWQiLGNhbmRpZGF0ZSk7CiAgICBlbHNlCiAgICAgICAgcHJpbnRmKCJObyBtYWpvcml0eSBlbGVtZW50IGZvdW5kIik7Cn0KIAppbnQgbWFpbih2b2lkKQp7CiAgICBpbnQgYXJyW10gPSB7MiwyLDIsMyw0LDUsNiw3fTsKIAogICAgcHJpbnRNYWpvcml0eUVsZW1lbnQoYXJyLCA4KTsKIAogICAgcmV0dXJuIDA7Cn0=