Write a program to find the majority element in an array in Python

Problem : Find the majority element in an array. An element that dominates in array A[] with array size n is the element that occurs more than n/2 times.

Example :

Input : {3, 3, 4, 2, 4, 4, 2, 4, 4} Output : 4 Giải thích: Tần suất xuất hiện của 4 là 5 lớn hơn một nửa kích thước của mảng. Input : {3, 3, 4, 2, 4, 4, 2, 4} Output : Không có phần tử chiếm đa số Giải thích: Không có phần tử nào có tần suất xuất hiện lớn hơn một nửa kích thước của mảng.

In this article, TipsMake.com will learn with you how to write a program to determine the majority element in the Python programming language.

Method 1: The simplest way to handle it

The most basic solution is to use two loops to count the maximum number of occurrences of all different elements. If the maximum number of occurrences is greater than n/2, stop the loop and return the element with the maximum number of occurrences. If the maximum number of occurrences is not greater than n/2 then the majority element does not exist.

Illustrated solution:

arr[] = {3, 4, 3, 2, 4, 4, 4, 4}, n = 8 For i = 0: count = 0 - Lặp qua toàn bộ mảng, khi một phần tử bằng với arr[i] (là 3), tăng count - count của arr[i] là 2, số này nhỏ hơn n/2, do vậy nó không phải là phần tử chiếm đa số For i = 1: count = 0 - Lặp qua toàn bộ mảng, khi một phần tử bằng với arr[i] (là 4), tăng count - count của arr[i] là 5, số này lớn hơn n/2 (là 4), do vậy nó chính là phần tử chiếm đa số Kết luận, 4 là phần tử chiếm đa số.

Follow the steps below to resolve the issue:

1. Create a variable to store the maximum count, count = 0.
2. Browse the table from start to finish.
3. With an element in the array, run another loop to find the frequency of occurrence of similar elements in the given array.
4. If the count is greater than the maximum, update the maximum count and store the index in another variable.
5. If the maximum frequency is greater than half the size of the array, print the element. Otherwise, returns the message that the array has no majority element.

Here is the sample code for your reference:

# Python3 program to find Majority # element in an array # Function to find Majority # element in an array def findMajority(arr, n): maxCount = 0 index = -1 # sentinels for i in range(n): count = 0 for j in range(n): if(arr[i] == arr[j]): count += 1 # update maxCount if count of # current element is greater if(count > maxCount): maxCount = count index = i # if maxCount is greater than n/2 # return the corresponding element if (maxCount > n//2): print(arr[index]) else: print("No Majority Element") # Driver code if __name__ == "__main__": arr = [1, 1, 2, 1, 3, 5, 1] n = len(arr) # Function calling findMajority(arr, n) # This code is contributed # by ChitraNayal

Method 2: Use a binary search tree (BST)

Add each element to the BTS and if that element is present, increment the node count. At any stage, if the count of a node is greater than n/2 then print the element.

Follow the steps below to resolve the issue:

1. Create a binary search tree, if the same element is entered in the binary search tree, the node frequency will be increased.
2. Traverse the array and add the element to the binary search tree.
3. If the maximum frequency value of any node is greater than half the size of the array, perform an in-order traversal and find that node.
4. Otherwise, returns the array message without the majority element.

Here is the sample code for your reference:

# Python3 program to demonstrate insert operation in binary # search tree. # class for creating node class Node(): def __init__(self, data): self.data = data self.left = None self.right = None self.count = 1 # count of number of times data is inserted in tree # class for binary search tree # it initialises tree with None root # insert function inserts node as per BST rule # and also checks for majority element # if no majority element is found yet, it returns None class BST(): def __init__(self): self.root = None def insert(self, data, n): out = None if (self.root == None): self.root = Node(data) else: out = self.insertNode(self.root, data, n) return out def insertNode(self, currentNode, data, n): if (currentNode.data == data): currentNode.count += 1 if (currentNode.count > n//2): return currentNode.data else: return None elif (currentNode.data < data): if (currentNode.right): self.insertNode(currentNode.right, data, n) else: currentNode.right = Node(data) elif (currentNode.data > data): if (currentNode.left): self.insertNode(currentNode.left, data, n) else: currentNode.left = Node(data) # Driver code # declaring an array arr = [3, 2, 3] n = len(arr) # declaring None tree tree = BST() flag = 0 for i in range(n): out = tree.insert(arr[i], n) if (out != None): print(arr[i]) flag = 1 break if (flag == 0): print("No Majority Element")

Method 3: Use Moore's Voting algorithm

This is a 2 step process:

1. The first step gives the element that can be the majority element in the array. If there is a majority element in the array then this step will definitely return the element with the majority. Otherwise, it returns the candidate for the majority element.
2. The second step is to check whether the majority element obtained from the previous step is really the majority element. This step is necessary because there exists a case where there is no majority element.

Illustrated solution:

arr[] = {3, 4, 3, 2, 4, 4, 4, 4}, n = 8 maj_index = 0, count = 1 Ở i = 1: arr[maj_index] != arr[i] - count = count – 1 = 1 – 1 = 0 - now count == 0 then: - maj_index = i = 1 - count = count + 1 = 0 + 1 = 1 Ở i = 2: arr[maj_index] != arr[i] - count = count – 1 = 1 – 1 = 0 - now count == 0 then: - maj_index = i = 2 - count = count + 1 = 0 + 1 = 1 Ở i = 3: arr[maj_index] != arr[i] - count = count – 1 = 1 – 1 = 0 - now count == 0 then: - maj_index = i = 3 - count = count + 1 = 0 + 1 = 1 Ở i = 4: arr[maj_index] != arr[i] - count = count – 1 = 1 – 1 = 0 - now count == 0 then: - maj_index = i = 4 - count = count + 1 = 0 + 1 = 1 Ở i = 5: arr[maj_index] == arr[i] - count = count + 1 = 1 + 1 = 2 Ở i = 6: arr[maj_index] == arr[i] - count = count + 1 = 2 + 1 = 3 Ở i = 7: arr[maj_index] == arr[i] - count = count + 1 = 3 + 1 = 4 Do đó, arr[maj_index] có khả năng là ứng viên phần tử chiếm đa số. Bây giờ, duyệt lại toàn bộ mảng để kiểm tra xem arr[maj_index] có phải là phần tử chiếm đa số hay không. arr[maj_index] là 4 4 xuất hiện 5 lần trong mảng nên 4 là phần tử chiếm đa số.

Follow the steps below to resolve the issue:

1. Iterates over each element and maintains the count of the majority element (count) and the majority index maj_index.
2. If the next element is similar then increase count and if the next element is not similar then decrease count.
3. If count is 0, then change maj_index to the current element and set count back to 1.
4. Now continue to traverse the array and find the count of the found majority element.
5. If count is more than half the array size, return the element.
6. Otherwise, returns an array without a majority element.

Here is the sample code for your reference:

# Program for finding out majority element in an array # Function to find the candidate for Majority def findCandidate(A): maj_index = 0 count = 1 for i in range(len(A)): if A[maj_index] == A[i]: count += 1 else: count -= 1 if count == 0: maj_index = i count = 1 return A[maj_index] # Function to check if the candidate occurs more than n/2 times def isMajority(A, cand): count = 0 for i in range(len(A)): if A[i] == cand: count += 1 if count > len(A)/2: return True else: return False # Function to print Majority Element def printMajority(A): # Find the candidate for Majority cand = findCandidate(A) # Print the candidate if it is Majority if isMajority(A, cand) == True: print(cand) else: print("No Majority Element") # Driver code A = [1, 3, 3, 1, 2] # Function call printMajority(A)

Method 4: Use Hashing

In a Hashtable (key-value pair), at value maintains the count for each element (key) and whenever count is greater than half the length of the array, returns that key (the element that is the majority).

Illustrated solution:

arr[] = {3, 4, 3, 2, 4, 4, 4, 4}, n = 8 Tạo một hashtable cho mảng 3 -> 2 4 -> 5 2 -> 1 Duyệt qua toàn bộ hashtable - Count cho 3 là 2, nhỏ hơn n/2 (4) do vậy nó không thể là phần tử chiếm đa số. - Count cho 4 là 5, lớn hơn n/2 (4) do vậy 4 là phần tử chiếm đa số. Kết luận 4 là phần tử chiếm đa số.

Follow these steps to resolve the issue:

1. Create a hashtable containing key-value pairs. In this case key is the element while value is the frequency of occurrence of that element in the array.
2. Traverse the entire array from beginning to end.
3. For each element in the array, add the element to the hashtable if the element does not already exist as a key, otherwise load the value of the key (array[i]) and increment the value by 1.
4. If count is greater than half of the array size, return the majority element and terminate the program.
5. If not, return the message that the majority element was not found.

Here is the sample code for your reference:

# Python3 program for finding out majority # element in an array def findMajority(arr, size): m = {} for i in range(size): if arr[i] in m: m[arr[i]] += 1 else: m[arr[i]] = 1 count = 0 for key in m: if m[key] > size / 2: count = 1 print("Majority found :-",key) break if(count == 0): print("No Majority element") # Driver code arr = [2, 2, 2, 2, 5, 5, 2, 3, 3] n = len(arr) # Function calling findMajority(arr, n) # This code is contributed by ankush_953

Method 5: Use Sorting

The idea of ​​this method is to rearrange the array. Sorting causes similar elements in the array to be contiguous so iterate over the array and update the count until the current element is still the same as the previous one. If the frequency of an element is greater than half the size of the array, return the element that has the majority.

Illustrated solution:

arr[] = {3, 4, 3, 2, 4, 4, 4, 4}, n = 8 Mảng sau khi Sorting => arr[] = {2, 3, 3, 4, 4, 4, 4, 4}, count = 1 Ở i = 1: - arr[i] != arr[i – 1] => arr[1] != arr[0] - count không lớn hơn n/2, do đó thiết lập lại count, count = 1 Ở i = 2: - arr[i] == arr[i – 1] => arr[2] == arr[1] = 3 - count = count + 1 = 1 + 1 = 2 Ở i = 3 - arr[i] != arr[i – 1] => arr[3] != arr[2] - count không lớn hơn n/2, do đó thiết lập lại count, count = 1 Ở i = 4 - arr[i] == arr[i – 1] => arr[4] == arr[3] = 4 - count = count + 1 = 1 + 1 = 2 Ở i = 5 - arr[i] == arr[i – 1] => arr[5] == arr[4] = 4 - count = count + 1 = 2 + 1 = 3 Ở i = 6 - arr[i] == arr[i – 1] => arr[6] == arr[5] = 4 - count = count + 1 = 3 + 1 = 4 Ở i = 7 - arr[i] == arr[i – 1] => arr[7] == arr[6] = 4 - count = count + 1 = 4 + 1 = 5 Do count của 4 lớn hơn n/2 nên 4 là phần tử chiếm đa số.

Follow these steps to resolve the issue:

1. Sort the array and create a variable count and temp with temp = INT_MIN.
2. Iterate over all elements from beginning to end.
3. If the current element is equal to the previous element, increment count.
4. Otherwise, set count back to 1.
5. If count is more than half the size of the array, return the majority element and stop the program.
6. If not, return the message that there is no majority element.

Here is the sample code for your reference:

# Python3 program to find Majority # element in an array # Function to find Majority element # in an array # it returns -1 if there is no majority element def majorityElement(arr, n) : # sort the array in O(nlogn) arr.sort() count, max_ele, temp, f = 1, -1, arr[0], 0 for i in range(1, n) : # increases the count if the same element occurs # otherwise starts counting new element if(temp == arr[i]) : count += 1 else : count = 1 temp = arr[i] # sets maximum count # and stores maximum occurred element so far # if maximum count becomes greater than n/2 # it breaks out setting the flag if(max_ele < count) : max_ele = count ele = arr[i] if(max_ele > (n//2)) : f = 1 break # returns maximum occurred element # if there is no such element, returns -1 if f == 1 : return ele else : return -1 # Driver code arr = [1, 1, 2, 1, 3, 5, 1] n = len(arr) # Function calling print(majorityElement(arr, n)) # This code is contributed by divyeshrabadiya07

TipsMake.com hopes that this article will be useful to you.

Kareem Winters

Update 07 July 2023