Friday, 21 October 2016

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 :-

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

No comments:
Write comments

Recommended Posts × +