Table of Contents
Problem Statement
Given a sorted array, we need to find the majority element from the sorted array. Majority element: Number occurring more than half the size of the array. Here we have given a number x we have to check it is the majority_element or not.
Example
Input
5 2
1 2 2 2 4
Output
2 is a majority element
Approach 1 for finding Majority Element
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.
Implementation
C++ Program for finding Majority Element
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,x;
cin>>n>>x;
int arr[n];
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
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 a majority element\n";
else
cout<<x <<" is not a majority element\n";
return 0;
}Java Program for finding Majority Element
import java.util.Scanner;
class sum
{
public static int first(int arr[], int low, int high, int x, int n)
{
if (high >= low) {
int mid = low + (high - low) / 2;
if ((mid == 0 || x > arr[mid - 1]) && arr[mid] == x)
return mid;
else if (x > arr[mid])
return first(arr, (mid + 1), high, x, n);
else
return first(arr, low, (mid - 1), x, n);
}
return -1;
}
public static int last(int arr[], int low, int high, int x, int n)
{
if (high >= low) {
int mid = low + (high - low) / 2;
if ((mid == n - 1 || x < arr[mid + 1]) && arr[mid] == x)
return mid;
else if (x < arr[mid])
return last(arr, low, (mid - 1), x, n);
else
return last(arr, (mid + 1), high, x, n);
}
return -1;
}
public static void main(String[] args)
{
Scanner sr = new Scanner(System.in);
int n = sr.nextInt();
int x = sr.nextInt();
int a[] = new int[n];
for(int i=0;i<n;i++)
{
a[i] = sr.nextInt();
}
int low=first(a,0,n-1,x,n); //index of first occurence of the element
int high=last(a,0,n-1,x,n); //index of the last occurenece of element
if((high-low+1)>n/2)
System.out.println(x+" is a majority element");
else
System.out.println(x+" is not a majority element");
}
}5 2 1 2 2 2 4
2 is a majority element
Complexity Analysis
Time Complexity: O(logN) because we use the concept of binary search and we know that the binary search algorithm has O(long) time complexity.
Space Complexity: O(1) because we just use some variables which come under O(1) or constant space complexity.
Approach 2 for finding Majority Element
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.
Implementation
C++ Program
#include <bits/stdc++.h>
using namespace std;
int main()
{
int N,x;
cin>>N>>x;
int arr[N];
for(int i=0;i<N;i++)
{
cin>>arr[i];
}
int end;
if(N%2)
end = N/2+1;
else
end = N/2;
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";
}Java Program
import java.util.Scanner;
class sum
{
public static void main(String[] args)
{
Scanner sr = new Scanner(System.in);
int n = sr.nextInt();
int x = sr.nextInt();
int a[] = new int[n];
for(int i=0;i<n;i++)
{
a[i] = sr.nextInt();
}
int end;
if(n%2==1)
end = n/2+1;
else
end = n/2;
int temp=0;
for(int i=0;i<end;i++)
{
if(a[i] ==x && x == a[i+n/2])
{
System.out.println(x+" is a mojority element");
i=end;
temp=1;
}
}
if(temp==0)
System.out.println(x+" is not a majority element");
}
}5 2 1 2 3 3 6
2 is not a majority element
Complexity Analysis
Time Complexity: O(N) because we just traverse the half sub-array which is lead us to O(n) time complexity.
Space Complexity: O(1) because here we don’t use any auxiliary space.