Hey coder! So in this tutorial, we will be understanding a simple problem in the python programming language. The problem is very simple but can still be asked in many job interviews.
Understanding the Majority Element problem
In the program, the user needs to input an array A having N elements. The code then aims to find the majority element in the array.
The majority element in array A of size N is the element that appeared more than N/2 times in the array.
The program will either return the majority element or it will return -1 if there is no majority element found/present.
Implementing the Majority Element Finder in Python
In the code implementation, we would first take the input of the size of the array and then take all the elements of the array separated by a space.
Then we will be storing the count of each element in the array in form of a dictionary in which mapping of the element to the count of the element is done.
Lastly, we will be checking the count of each element with n/2, and whenever the count becomes greater than n/2 we return the number otherwise we return -1.
def check_majority(arr, N):
map = {}
for i in range(0, N):
if arr[i] in map.keys():
map[arr[i]] += 1
else:
map[arr[i]] = 1
for key in map:
if map[key] > (N / 2):
return key
return -1
arr = list(input("Enter elements of array:"))
size = len(arr)
ans = check_majority(arr, size)
if ans != -1:
print("Majority Element is: ", ans)
else:
print("No majority element in array")
Sample Outputs
Enter elements of array:1111111212121
Majority Element is: 1
Conclusion
I hope you are cleared with the problem statement and the code implementation. And yes there can be multiple ways of solving this same question. Can you think of any?
Happy learning! 😇