You are given an array
arr
of size
n
, write a program to find the element which appears more than
n/2
times in the array
arr
.
Problem Note
- Do not confuse the majority element as just the element with maximum frequency. A majority element occurs more than n/2 times.
- You may assume that the array is non-empty and if the majority element is not present in the array, return -1 (Assume -1 is not the element in the array) as the output.
Example 1
Input: arr[] = [8, 8, 8, 8, 8, 10, 10]
Output: 8
Explanation: Majority element 8 occurs 5 times which is greater than 7/2(n/2) in the above array. Hence, the output is 8.
Example 2
Input: arr[] = [20, 30, 40, 50, 20, 60, 10]
Output: -1
Explanation: No Majority element present in the above array. Hence, the output is -1.