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.
Table of Contents
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.
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; }
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.
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 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"; }
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.