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.