An array A[1... n] is said to have a majority element if more than half of its e

Question

An array A[1... n] is said to have a majority element if more than half of its entries are the same. Given an array, design an efficient algorithm to tell whether the array has a majority element, and, if so, to find that element. The elements of the array are not necessarily from some ordered domain like the integers, and so there can be no comparisons of the form "is A[i] > A[j]?". (As an example, think of the array elements as PDF files.) However, you can answer questions of the form "is A[i] = A[j]?" in constant time. Give a Theta(n log n) divide-and-conquer algorithm to solve this problem. Remember, a complete answer includes an algorithm description, an algorithm, and a analysis.

Explanation / Answer

There can be different approach to solving this problem.
First Approach

We will use binary search tree for this process. The nodes of binary search tree will be used in this approach.
Steps:
1.   Start inserting elements in BST one by one.
2.   If element is already present then we will increment the count of node.
3.   Now if the count of node becomes moe than n/2 then it means majority element is present.

Complexity in this case will be O(n^2). To make its complexity O(nlogn) we will need to use self balancing BST.

Second Approach:
This will use Moore's Voting Algorithm
Two steps.
>   Get the element with most occurence in the array
>   Check whether it is majority element.

1. Finding the element: Moore Voting Slgo will be used here. In this we cancel out the occurence of an element x with differrent other elements which are not x. Now if x remains then it is majority element.

2. Check if element is majority: If the occurence of element is more than n/2 then it is majority element.

Implementation:

#include<stdio.h>
# define bool int

bool isMajorityElement(int *, int, int);
int findCandidateElement(int *, int);

int findCandidateElement(int a[], int size)
{
   int maj_index = 0, count = 1;
   int p;
   for (p = 1; p < size; p++)
   {
       if (a[maj_index] == a[p])
           count++;
       else
           count--;
       if (count == 0)
       {
           maj_index = p;
           count = 1;
       }
   }
   return a[maj_index];
}

void printMajorityElement(int a[], int size)
{

int candid = findCandidateElement(a, size);

/* Print the candidate if it is Majority*/
if (isMajorityElement(a, size, candid))
   printf(" %d ", candid);
else
   printf("No Majority Element");
}
bool isMajorityElement(int a[], int size, int candid)
{
   int p, count = 0;
   for (p = 0; p < size; p++)
   if (a[p] == candid)
       count++;
   if (count > size/2)
   return 1;
   else
   return 0;
}

int main()
{
   int a[] = {2, 5, 6, 2, 2, 5 , 5, 5, 8, 6, 3,5,6,2,7};
   int n = (sizeof(a))/sizeof(a[0]);
   printMajorityElement(a, n);
   getchar();
   return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.