Home » Technical Interview Questions » Array Interview Questions » Majority Element

Majority Element


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.

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

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.

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!!

You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Abhishek

Abhishek was able to crack Microsoft after practicing questions from TutorialCup