Majority Element

Posted in

Majority Element

Vinay Khatri
Last updated on June 9, 2022

    We have been given an integer array of size ‘n’, we have to print the majority element of the given array and, if no majority element exists then we need to print “No majority element exists.” The majority element is defined as the element which occurs more than n/2 times in the array. It can be easily observed that at max 1 majority element can exist for a particular array. Example 1-

    Input - a[] = {5, 8, 3, 5, 5, 2, 5}
    Output - 5

    Explanation - 5 appears 4 times and as 4>(7/2) we conclude that 5 is our majority element. Example 2 -

    Input - a[]={9, 3, 2, 9, 5}
    Output - No majority element exists.

    Explanation - We can observe that no element is occurring more than n/2 i.e. 2 times.

    Simple Approach (Brute Force)

    The idea is to count the frequency of every element by running two nested loops and if we find any element repeating more than n/2 times then we print that and break our loops. If even after traversing the whole array we didn’t find any majority element we simply print “No majority element exists.” Below is the implementation of the above approach -

    C++ Programming

    #include <bits/stdc++.h>
    using namespace std;
    void printMajoriyElementIfExists(int a[],int n){
        
        // Outer loop to
        // traverse the array.
        for(int i=0;i<n;i++)
        {
            int count=0;
            // Inner loop to
            // count frequency 
            // of a[i]. 
            for(int j=i;j<n;j++) { if(a[j]==a[i]) count++; } // If count>n/2
            // it means a[i]
            // is a Majority element.
            if(count>n/2)
            {
                cout<<a[i]<<" is the Majority element.";
                return;
            }
        }
        
        // If execution reaches here 
        // it means no Majority element exists.
        cout<<"No Majority element exists.";
        
    }
    int main() {
    	int arr[] = {5, 8, 3, 5, 5, 2, 5};
        int n = sizeof(arr)/sizeof(arr[0]);
        
        printMajoriyElementIfExists(arr,n);
        
        cout<<endl;
    	return 0;
    }
    

    Output:

    5 is the Majority element.

    Java Programming

    import java.util.*;
    public class Main{
        public static void printMajoriyElementIfExists(int a[],int n){
            
            // Outer loop to
            // traverse the array.
            for(int i=0;i<n;i++)
            {
                int count=0;
                // Inner loop to
                // count frequency 
                // of a[i]. 
                for(int j=i;j<n;j++) 
                { 
                   if(a[j]==a[i]) 
                      count++; 
                } 
                // If count>n/2
                // it means a[i]
                // is Majority element.
                if(count>n/2)
                {
                    System.out.print(a[i]+" is the Majority element.");
                    return;
                }
            }
            
            // If execution reaches here 
            // it means no Majority element exists.
            System.out.print("No Majority element exists.");
            
        }
        public static void main(String[] args){
     
            int arr[] = {5, 8, 3, 5, 5, 2, 5};
            int n = arr.length;
            
            printMajoriyElementIfExists(arr,n);
            
            System.out.println();
        }    
    }
    

    Output:

    5 is the Majority element.

    Python Programming

    def printMajoriyElementIfExists(arr, n):
     
        # Outer loop to
        # traverse the array.
        for i in range(n):
     
            count = 0
            # Inner loop to
            # count frequency 
            # of a[i]. 
            for j in range(n):
     
                if(arr[i] == arr[j]):
                    count +=1
     
            # If count>n/2
            # it means a[i]
            # is Majority element.
            if (count > n/2):
                print(arr[i], "is the Majority element.")
                return
        # If execution reaches here 
        # it means no Majority element exists.
        print("No Majority Element exists.")
     
     
    # Driver code
    if __name__ == "__main__":
        arr = [5, 8, 3, 5, 5, 2, 5]
        n = len(arr)
     
        # Function calling
        printMajoriyElementIfExists(arr, n)
        print()
    

    Output:

    5 is the Majority element.

    Complexity Analysis

    • Time Complexity : O(n^2), Because in the worst case we have to make n^2 operations.
    • Extra Space : O(1), Since we didn't use any extra space.

    Another Approach

    In this approach, the idea of sorting is used. We can observe that after sorting equal elements become adjacent. For an example array - {5, 8, 3, 5, 5, 2, 5} becomes {2, 3, 5, 5, 5, 5, 8}. Have a look at the algorithm for better understanding -

    Algorithm:

    1. Sort the given array.
    2. Create a variable freq to store the frequency of an element, initialize it with 1.
    3. Traverse array from 1 to n-1.
    4. If the current element is equal to the previous element then we will increase our freq else we will make freq=1.
    5. During each iteration, we will check if freq>n/2 then we will print the current element as the majority element.
    6. At last, if we didn’t encounter any majority element then we will print no majority element exists.

    Below is the implementation of the above approach -

    C++ Programming

    #include <bits/stdc++.h>
    using namespace std;
    void printMajoriyElementIfExists(int a[],int n){
            // If size of array is 
            // 1 then the first element
            // is a Majority element.
            if(n==1)
            {
                cout<<a[0]<<" is the Majority element.";
                return;
            }
            
            // Sort the array.
            sort(a,a+n);
            // Initialize freq with 1.
            int freq=1;
            for(int i=1;i<n;i++) 
            { 
                // If previous element 
                // is equal to current 
                // increase freq. else // make it 1. 
                if(a[i]==a[i-1]) 
                   freq++; 
                else 
                   freq=1; 
                // If freq>n/2 at
                // any point of time.   
                // it means it is Majority
                // element.
                if(freq>n/2)
                {
                    cout<<a[i]<<" is the Majority element.";
                    return;
                }
            }
            
            cout<<"No Majority element exists.";
        
    }
    int main() {
    	int arr[] = {5, 8, 3, 5, 5, 2, 5};
        int n = sizeof(arr)/sizeof(arr[0]);
        
        printMajoriyElementIfExists(arr,n);
        
        cout<<endl;
    	return 0;
    }
    

    Output:

    5 is the Majority element.

    JAVA:

    import java.util.*;
    public class Main{
        public static void printMajoriyElementIfExists(int a[],int n){
            // If size of array is 
            // 1 then the first element
            // is Majority element.
            if(n==1) 
            {
                System.out.print(a[0]+ " is the Majority element.");
                return;
            }
            
            // Sort the array.
            Arrays.sort(a);
            // Initialize freq with 1.
            int freq=1;
            for(int i=1;i<n;i++) 
            { 
                // If previous element 
                // is equal to current 
                // increase freq. else 
                // make it 1. 
                if(a[i]==a[i-1]) 
                    freq++; 
                else 
                    freq=1; 
                // If freq>n/2 at
                // any point of time.   
                // it means it is Majority
                // element.
                if(freq>n/2)
                {
                    System.out.print(a[i]+ " is the Majority element.");
                    return;
                }
            }
            
            System.out.print("No Majority element exists.");
            
        }
        public static void main(String[] args){
     
            int arr[] = {5, 8, 3, 5, 5, 2, 5};
            int n = arr.length;
            
            printMajoriyElementIfExists(arr,n);
            
            System.out.println();
            
        }    
    }
    

    Output:

    5 is the Majority element.

    Python Programming

    def printMajoriyElementIfExists(arr, n) :
        # If size of array is 
        # 1 then the first element
        # is a Majority element.
        if(n==0):
            print(arr[0], "is the Majority element.")
            return
        # Sort the array.
        arr.sort()  
        #  Initialize freq with 1.
        freq=1
        for i in range(1, n) :
             
            # If previous element
            # is equal to current
            # increase freq. else
            # make it 1.
            if(arr[i-1] == arr[i]) :
                freq += 1
            else :
                freq = 1
            # If freq>n/2 at
            # any point of time.   
            # it means it is Majority
            # element.
            if(freq>n/2):
                print(arr[i], "is the Majority element.")
                return
                 
        print("No Majority element exists.")
     
    # Driver code
    if __name__ == "__main__":
        arr = [5, 8, 3, 5, 5, 2, 5]
        n = len(arr)
     
        # Function calling
        printMajoriyElementIfExists(arr, n)
        print()
    

    Output:

    5 is the Majority element.

    Complexity Analysis

    • Time Complexity: O(nlogn). Since sorting takes O(n log n) time.
    • Extra Space: O(1). Since no extra space is required.

    Efficient Approach

    In this idea we will use hashing, a HashMap to be exact. We can store the frequency of each element in our HashMap by traversing the array once. And during another traversal, we can print the element with a frequency of more than n/2. Have a look at the algorithm for better understanding -

    Algorithm:

    1. Create a HashMap
    2. Traverse the array, and update the frequency of elements each time.
    3. Again traverse the array from 0 to n-1.
    4. If any element’s frequency is greater than n/2 print it.
    5. If we did not find any majority element it means the array does not contain any majority element.

    Below is the implementation of above approach -

    C++ Programming

    #include <bits/stdc++.h>
    using namespace std;
    void printMajoriyElementIfExists(int a[],int n){
            // Create a HashMap
            unordered_map<int, int> hm;
            // Find frequency of each element.
            for(int i=0;i<n;i++)
            {
                hm[a[i]]++;
            }
            // Check if any element's
            // frequency is greater
            // than n/2.
            for(int i=0;i<n;i++) 
            { 
                auto temp=hm.find(a[i]); 
                if(temp->second>n/2)
                {
                    cout<<a[i]<<" is the Majority element.";
                    return;
                }
            }
            cout<<"No Majority element exists.";
        
    }
    int main() {
    	int arr[] = {5, 8, 3, 5, 5, 2, 5};
        int n = sizeof(arr)/sizeof(arr[0]);
        
        printMajoriyElementIfExists(arr,n);
        
        cout<<endl;
    	return 0;
    }
    

    Output:

    5 is the Majority element.

    Java Programming

    import java.util.*;
    public class Main{
        public static void printMajoriyElementIfExists(int a[],int n){
            
            // Create a HashMap
            HashMap<Integer,Integer> hm=new HashMap<>();
            
            // Find frequency of each element.
            for(int i=0;i<n;i++) 
            {
                hm.put(a[i],hm.get(a[i])==null?1:hm.get(a[i])+1);
            }
            
            // Check if any element's
            // frequency is greater
            // than n/2.
            for(int i=0;i<n;i++) 
            { 
                if(hm.get(a[i])>n/2)
                {
                    System.out.print(a[i]+" is the majority element.");
                    return;
                }
            }
            System.out.print("No majority element exists.");
            
        }
        public static void main(String[] args){
     
            int arr[] = {5, 8, 3, 5, 5, 2, 5};
            int n = arr.length;
            
            printMajoriyElementIfExists(arr,n);
            
            System.out.println();
            
        }    
    }
    

    Output:

    5 is the Majority element.

    Python Programming

    def printMajoriyElementIfExists(a, n) :
        # Create a HashMap
        m = {}
        # Find frequency of each element.
        for i in range(n):
            if a[i] in m:
                m[a[i]] += 1
            else:
                m[a[i]] = 1
        # Check if any element's
        # frequency is greater
        # than n/2.
        for key in m:
            if m[key] > n / 2:
                print(a[i], "is the Majority element.")
                return
        
        print("No Majority element exists.")
     
    # Driver code
    if __name__ == "__main__":
        arr = [5, 8, 3, 5, 5, 2, 5]
        n = len(arr)
     
        # Function calling
        printMajoriyElementIfExists(arr, n)
        print()
    

    Output:

    5 is the Majority element.

    Complexity Analysis:

    • Time Complexity: O(n). Since only two traversals of the array are needed.
    • Auxiliary Space : O(n). Since a hashmap is used.

    Optimal Approach

    This approach is based on Moore’s Voting algorithm. This involves two steps: in the first step we check for a potential element that can be our answer and in step 2 we will check if that element is a majority element or not. Let’s look at the algorithm to have a better understanding -

    Algorithm:

    1. To check for potential elements, we will maintain two variables i.e. ‘ind’ and ‘freq’, and initialize them with 0 and 1.
    2. We will traverse the array if a[ind]=a[i] we will increase our freq else we will decrease it. Once freq reaches zero we will update freq and ind with 1 and i respectively.
    3. After traversing we have a[ind] as our potential answer.
    4. Now we will check if a[ind] is actually our answer or not.
    5. If it is then we will print that element as our majority element otherwise we can conclude no majority element exists in the array.

    Below is the implementation of above approach -

    C++ Programming:

    #include <bits/stdc++.h>
    using namespace std;
    int findPotentialAnswer(int a[],int n){
            
        // Initialize ind and
        // freq with 0 and 1.
        int ind=0,freq=1;
        for(int i=0;i<n;i++)
        {
            // Increase freq
            // if condition statisfy.
            if(a[i]==a[ind])
            {
                freq++;
            }
            else
            freq--;
            
            // If freq==0
            // then change accordingly. 
            if(freq==0)
            {
                freq=1;
                ind=i;
            }
        }
    
        return a[ind];
    }
    void printMajoriyElementIfExists(int a[],int n){
        // Find the potential_answer.
        int potential_answer=findPotentialAnswer(a,n);
        
        // Check whether the
        // potential_answer is
        // actually Majority
        // element or not.
        int count=0;
        for(int i=0;i<n;i++) 
        { 
            if(a[i]==potential_answer) 
              count++; 
        } 
        // If count>n/2
        // it means that it 
        // is the Majority element.
        if(count>n/2)
        cout<<potential_answer<<" is the Majority element.";
        else
        cout<<"No Majority element exists.";
           
        
    }
    int main() {
    	int arr[] = {5, 8, 3, 5, 5, 2, 5};
        int n = sizeof(arr)/sizeof(arr[0]);
        
        printMajoriyElementIfExists(arr,n);
        
        cout<<endl;
    	return 0;
    }
    

    Output:

    5 is the Majority element.

    Java Programming

    import java.util.*;
    public class Main {
        public static void printMajoriyElementIfExists(int a[],int n){
            
            // Find the potential_answer.
            int potential_answer=findPotentialAnswer(a,n);
            
            // Check wether the
            // potential_answer is
            // actually Majority
            // element or not.
            int count=0;
            for(int i=0;i<n;i++) 
            {
            if(a[i]==potential_answer) 
               count++; 
            } 
            // If count>n/2
            // it means that it 
            // is the Majority element.
            if(count>n/2)
            System.out.print(potential_answer+" is the Majority element.");
            else
            System.out.print("No Majority element exists.");
        }
        public static int findPotentialAnswer(int a[],int n){
            
            // Initialize ind and
            // freq with 0 and 1.
            int ind=0,freq=1;
            for(int i=0;i<n;i++)
            {
                // Increase freq
                // if condition statisfy.
                if(a[i]==a[ind])
                {
                    freq++;
                }
                else
                freq--;
                
                // If freq==0
                // then change accordingly. 
                if(freq==0)
                {
                    freq=1;
                    ind=i;
                }
            }
        
            return a[ind];
        }
    	public static void main (String[] args) {
    		int arr[] = {5, 8, 3, 5, 5, 2, 5};
            int n = arr.length;
            
            printMajoriyElementIfExists(arr,n);
        	System.out.println();
    	
    	}
    }
    

    Output:

    5 is the Majority element.

    Python Programming:

    def findPotentialAnswer(A):
        # Initialize ind and
        # freq with 0 and 1.
        ind = 0
        freq = 1
        for i in range(len(A)):
            # Increase freq
            # if condition statisfy.
            if A[ind] == A[i]:
                freq += 1
            else:
                freq -= 1
            # If freq==0
            # then change accordingly. 
            if freq == 0:
                ind = i
                freq = 1
        return A[ind]
     
    def isMajority(A, cand):
        count = 0
        # If count>n/2
        # it means that it 
        # is the Majority element.
        for i in range(len(A)):
            if A[i] == cand:
                count += 1
        if count > len(A)/2:
            return True
        else:
            return False
    
    def printMajoriyElementIfExists(arr):
        # Find the potential_answer.
        potential = findPotentialAnswer(arr)
     
        # Print the potential if it is Majority
        if isMajority(arr, potential) == True:
            print(potential, "is the Majority Element.")
        else:
            print("No Majority Element exists")
     
     
    # Driver code
    arr = [5, 8, 3, 5, 5, 2, 5]
    printMajoriyElementIfExists(arr)
    

    Output:

    5 is the Majority element.

    Complexity Analysis:

    • Time Complexity : O(n), Since only two traversals of the array, is needed.
    • Extra Space : O(1), Because we only used variables.

    Wrapping Up!

    In this article, we have learned how to find the “Majority Element”. We discussed four approaches in which we can solve this problem. This article also contains well-explained codes of both the approaches in the three most popular languages which are c++, Java, and python, and their respective outputs attached to the article for a better understanding of a wide range of our readers. We sincerely hope that this article has walked you through some deep and important concepts of Arrays, Hashing, sorting and you have learned how we should approach such kinds of problems. We hope that you will now be able to solve this problem as well as its other variations seamlessly and efficiently. Happy Coding! People are also reading:

    Leave a Comment on this Post

    0 Comments