Majority Element

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.

References