Array ( [0] => [1] => questions [2] => Basic [3] => Majority-Element- )
Given an array of integers have to find the majority element if exists. A element is said to be Majority Element only if the element which has to be occurred more than the half of the size of the array.
First line contains the size of the array Next line contains the n integers separated by space.
Print the Majority element, if doesn’t exist return Null.
5 1 1 1 1 1
1
3 1 2 2
2
6 2 5 5 4 1 3
Null
Login to see Discussion
Approach 1: Using HashMap
Step-i) Initialize a empty hashmap.
Step-ii) Iterate the array and take every element as a.
Step-iii) If a is not present in the hashmap, intialize a in hashmap as 0
Step-iv) If a is already present increase it’s value by 1.
Step-v) Now the hash map is of frequency of every element.
Step-vi) Iterate through the hash map and check for frequency of every element is greater than half the length of the array.
Time Complexity: O(n)
Space Complexity: O(n)
Note :
Let us know if you can come up with a better approach, mail us at support@theinquisitive.in Your approach will be reviewed and posted with credits to you.
Login to see Solution