C++ Program To Find Element That Appears More Than N/2 Times.

Problem :- A Majority Element In An Array A[] of Size N Is An Element That Appears More Than N/2 (and hence there is at most one such element). Times. Write a Function Which Takes An Array And Emits The Majority Element (if it exists), Otherwise Prints NONE .

Logic :- We Need to print the Element Which repeat more than N/2 time's example if the size of array is 9 than number should be repeated at-least 5 times 

Let Take A Array 

Size =9

Array Element is 1 1 2 3 1 5 1 1 6

Now N/2 times should be 5 ,So here only 1 is a element only repeated more than N/2.

So Candidate Key is 1. 

Solution :-

#include<bits/stdc++.h>

using namespace std;

int majority(int a[],int size)

{

    int maj_index=0,count=1;

   

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

    {

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

        count++;

    else

      count--;

    if(count==0)

    {

      maj_index=i;

      count=1;

    }

    }

    return a[maj_index];

}

bool ismejority(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;

}

int main()

{

  int a[100],i,n;

    

cout<<"Enter The Size of An Array\n";

    cin>>n;

  

  cout<<"\nEnter The "<<n<<" Elemnts \n";

  

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

  cin>>a[i];  

    

  int cand=majority(a,n);

    

  if(ismejority(a,n,cand))

      cout<<"Candidate key \n"<<cand;

    else

      cout<<"key is not found";

   return 0;

}

Output :-