Skip to content

Instantly share code, notes, and snippets.

@SuryaPratapK
Created January 28, 2020 16:10
Show Gist options
  • Save SuryaPratapK/e53c468c3f6cc6b804f7b71d16928605 to your computer and use it in GitHub Desktop.
Save SuryaPratapK/e53c468c3f6cc6b804f7b71d16928605 to your computer and use it in GitHub Desktop.
/* 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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment