Find the majority element from the sorted array

Rahul

December 27, 2019

151

Given a sorted array, we need to find if a given x is a majority element.

Majority element: Number occurring more than half the size of the array.

INPUT: 1 2 2 2 4

OUTPUT: 2 IS A MAJOR ELEMENT

Method 1

TIME COMPLEXITY: O(logN)

SPACE COMPLEXITY: O(1)

We use the concept of Binary Search but in a tricky manner. The binary search can be modified easily to check the first occurrence of the given number x.

Algorithm

1. Check if the middle element of array is x or not .Because any majority element must be at middle of array if it occurs more than N/2 times.
2. If present then do a custom Binary Search to find the first occurrence of x.
3. The index obtained is say k,then check if (k+N/2)th index also has x. If yes then x is a majority element.

NOTE: Use lower_bound and higher_bound STL functions to do the task easily.

Program for Method 1

#include<bits/stdc++.h>
using namespace std;

int main()
{		
	int arr[] = {1,2,2,2,4};
	int N = sizeof(arr)/sizeof(arr[0]);	
	int x;
	
	//the element to be checked for majority element
	cin>>x;
	
	int low=lower_bound(arr,arr+N,x)-arr; //index of first occurence of the element
	int high=upper_bound(arr,arr+N,x)-arr; //index of the last occurenece of element
	
	if(high-low>N/2)
		cout<<x <<" is Majority element\n";
	else
		cout<<x <<" is not a Majority element\n";
	return 0;
}

Try It

Method 2

TIME COMPLEXITY: O(N)

SPACE COMPLEXITY: O(1)

Algorithm

Loop till the half of the array doing :
a. If the present element is x then check if (the present index + N/2)th index contains x.
b. If it does then x is a majority element.
c. Else x is not a majority element.

Program for Method 2

#include <bits/stdc++.h>
using namespace std;

int main()
{	
	int arr[] = {1,2,2,2,4};
	int N = sizeof(arr)/sizeof(arr[0]);	
		
	int end;
	if(N%2)
		end = N/2+1;
	else
		end = N/2;
	
	int x;
	
	cin>>x; //the element to be checked for majority element
		
	for(int i=0;i<end;i++)
	{
		if(arr[i] ==x and x == arr[i+N/2])
		{
			cout << x <<" is a mojority element "	<<endl;
			return 0;
		}
	}
	
	cout<<x<<" is not a majority element\n";
}

Try It