Majority Element

QUESTION

Write a program to find the majority element in the array. A majority element in an array A[] of size n is an element that appears more than n/2 times (and hence there is at most one such element). If input array doesn’t contain a majority element, then output \”NO Majority Element\”\n\nInput: The first line of the input contains T denoting the number of testcases. The first line of the test case will be the size of array and second line will be the elements of the array.\nOutput: For each test case the output will be the majority element of the array.\nConstraints:\n\n1 <=T<= 100\n\n1 <=N<= 100\n\n0 <= a[i]<= 100.

“TESTCASE_1”: “2\n5\n3 1 3 3 2\n3\n1 2 3\n###—###SEPERATOR—###—\n3\nNO Majority Element”, “TESTCASE_2”: “2\n7\n1 4 1 3 1 2 1\n5\n1 3 2 3 3\n###—###SEPERATOR—###—\n1\n3”, “TESTCASE_3”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

ANSWER

# include<stdio.h>
# define bool int
 
int findCandidate(int *, int);
bool isMajority(int *, int, int);
 
/* 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))
    printf("%d\n", cand);
  else
    printf("NO Majority Element\n");
}
 
/* Function to find the candidate for Majority */
int findCandidate(int a[], int size)
{
    int maj_index = 0, count = 1;
    int i;
    for (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 i, count = 0;
    for (i = 0; i < size; i++)
      if (a[i] == cand)
         count++;
    if (count > size/2)
       return 1;
    else
       return 0;
}
 
/* Driver function to test above functions */
int main()
{
  int t;
  scanf("%d", &t);
  while(t--)
  {
    int size;
    scanf("%d", &size);
    int a[size], i;
    for(i=0; i<size; i++)
      scanf("%d", &a[i]);
    printMajority(a, size);
    getchar();
  }
    return 0;
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro