You are given an array A[ ] of size n, write a program to find the number which appears more than n/2 times.

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).

Example 1

Input: A[] = [3, 2, 3]
Output: 3
Explanation: Majority element 3 occurs 2 times which is greater than 3/2.

Example 2

Input: A[] = [20,30,40,50,20,60,10]
Output: -1
Explanation: No Majority element present.