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;
}