Dominator of an array ...Majority Element In Different Way

Majority Element Different Possible Solutions


Solution 1: A basic solution is to scan entire array for checking for every element in the array. If any element occurs more than n/2 time, prints it and break the loop. This will be of O(n^2) complexity.

Solution 2: Sort the entire array in O(nlogn) and then in one pass keep counting the elements. This will be of O(nlogn) + O() = O(nlogn) complexity. #try it

Solution 3 Using BitCount Array

#include
int findmaj(int arr[], int n)
{
int bitcount[32];
int i, j, x;

for(i = 0; i < 32; i++)
bitcount[i] = 0;
for (i = 0; i < n; i++)
for (j = 0; j < 32; j++)
if (arr[i] & (1 << j)) // if bit j is on
bitcount[j]++;
else
bitcount[j]--;

x = 0;
for (i = 0; i < 32; i++)
if (bitcount[i] > 0)
x = x | (1 << i);
return x;
}

int main()
{
int i;
int arr[5] = {1, 3 ,1, 1, 3};

printf(" %d ", findmaj(arr, 5));

getchar();
return 0;
}

We keep a count of frequency of each of the bits. Since majority element will dominate the frequency count, hence we can get its value.

The solution is constant space and linear time : O(n)

Method 4 (Using Binary Search Tree)

Node of the Binary Search Tree (used in this approach) will be as follows. ?
struct tree
{
int element;
int count;
}BST;

Insert elements in BST one by one and if an element is already present then increment the count of the node. At any stage, if count of a node becomes more than n/2 then return.
The method works well for the cases where n/2+1 occurrences of the majority element is present in the starting of the array, for example {1, 1, 1, 1, 1, 2, 3, 4}.

Time Complexity: If a binary search tree is used then time complexity will be O(n^2). If a self-balancing-binary-search tree is used then O(nlogn)
Auxiliary Space: O(n)

METHOD 5 (Using Moore’s Voting Algorithm)

This is a two step process.
1. Get an element occurring most of the time in the array. This phase will make sure that if there is a majority element then it will return that only.
2. Check if the element obtained from above step is majority element.

1. Finding a Candidate:
The algorithm for first phase that works in O(n) is known as Moore’s Voting Algorithm. Basic idea of the algorithm is if we cancel out each occurrence of an element e with all the other elements that are different from e then e will exist till end if it is a majority element.

findCandidate(a[], size)
1. Initialize index and count of majority element
maj_index = 0, count = 1
2. Loop for i = 1 to size – 1
(a)If a[maj_index] == a[i]
count++
(b)Else
count--;
(c)If count == 0
maj_index = i;
count = 1
3. Return a[maj_index]

Above algorithm loops through each element and maintains a count of a[maj_index], If next element is same then increments the count, if next element is not same then decrements the count, and if the count reaches 0 then changes the maj_index to the current element and sets count to 1.
First Phase algorithm gives us a candidate element. In second phase we need to check if the candidate is really a majority element. Second phase is simple and can be easily done in O(n). We just need to check if count of the candidate element is greater than n/2.

Example:
A[] = 2, 2, 3, 5, 2, 2, 6
Initialize:
maj_index = 0, count = 1 –> candidate ‘2?
2, 2, 3, 5, 2, 2, 6

Same as a[maj_index] => count = 2
2, 2, 3, 5, 2, 2, 6

Different from a[maj_index] => count = 1
2, 2, 3, 5, 2, 2, 6

Different from a[maj_index] => count = 0
Since count = 0, change candidate for majority element to 5 => maj_index = 3, count = 1
2, 2, 3, 5, 2, 2, 6

Different from a[maj_index] => count = 0
Since count = 0, change candidate for majority element to 2 => maj_index = 4
2, 2, 3, 5, 2, 2, 6

Same as a[maj_index] => count = 2
2, 2, 3, 5, 2, 2, 6

Different from a[maj_index] => count = 1

Finally candidate for majority element is 2.

First step uses Moore’s Voting Algorithm to get a candidate for majority element.

2. Check if the element obtained in step 1 is majority

printMajority (a[], size)
1. Find the candidate for majority
2. If candidate is majority. i.e., appears more than n/2 times.
Print the candidate
3. Else
Print "NONE"

# include<stdio.h>
# define bool int

int findCandidate(int *, int);
bool isMajority(int *, int, int);

void printMajority(int a[], int size)
{
int cand = findCandidate(a, size);

if(isMajority(a, size, cand))
printf(" %d ", cand);
else
printf("NO Majority Element");
}

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

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

int main()
{
int a[] = {1, 3, 3, 1,1,1,2,3,1,2,1,1};
printMajority(a, 12);
getchar();
return 0;
}

Time Complexity: O(n)
Auxiliary Space : O(1)
Run Here http://ideone.com/ALf5fY