Majority Element

CODE

Majority Element

METHOD 1 (Basic)

// C++ program to find Majority

// element in an array

#include <bits/stdc++.h>

using namespace std;

// Function to find Majority element

// in an array

void findMajority(int arr[], int n)

{

    int maxCount = 0;

    int index = -1; // sentinels

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

    {

        int count = 0;

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

        {

            if(arr[i] == arr[j])

            count++;

        }

        // update maxCount if count of

        // current element is greater

        if(count > maxCount)

        {

            maxCount = count;

            index = i;

        }

    }

    // if maxCount is greater than n/2

    // return the corresponding element

    if (maxCount > n/2)

       cout << arr[index] << endl;

    else

        cout << "No Majority Element" << endl;

}

// Driver code

int main()

{

    int arr[] = {1, 1, 2, 1, 3, 5, 1};

    int n = sizeof(arr) / sizeof(arr[0]);

    // Function calling

    findMajority(arr, n);

    return 0;

}

Output :

1

METHOD 2 (Using Moore’s Voting Algorithm)

/* C++ Program for finding out

   majority element in an array */

#include <bits/stdc++.h>

using namespace std;

/* Function to find the candidate for Majority */

int findCandidate(int a[], int size)

{

    int maj_index = 0, count = 1;

    for (int i = 1; i < size; i++)

    {

        if (a[maj_index] == a[i])

            count++;

        else

            count--;

        if (count == 0)

        {

            maj_index = i;

            count = 1;

        }

    }

    return a[maj_index];

}

/* Function to check if the candidate

   occurs more than n/2 times */

bool isMajority(int a[], int size, int cand)

{

    int count = 0;

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

    if (a[i] == cand)

    count++;      

    if (count > size/2)

    return 1;  

    else

    return 0;

}

/* Function to print Majority Element */

void printMajority(int a[], int size)

{

   /* Find the candidate for Majority*/

   int cand = findCandidate(a, size);

   /* Print the candidate if it is Majority*/

   if (isMajority(a, size, cand))

   cout << " " << cand << " ";

   else

   cout << "No Majority Element";

}

 /* Driver function to test above functions */

int main()

{

    int a[] = {1, 3, 3, 1, 2};

    int size = (sizeof(a))/sizeof(a[0]);

    // Function calling

    printMajority(a, size);

    return 0;

}

Output:

No Majority Element