Element which occurred at least M/2 times.

Given an array of n integers, where one element appears more than n/2 times. We need to find that element in linear time and constant extra space.

Don’t need to worry about the case when there are no elements with freq > m/2. There are multiple ways to solve the problem.

One approach is Find the median, it takes O(n) on an unsorted array(Kth smallest element approach). Since more than n/2 elements are equal to the same value, the median is equal to that value as well.

Another approach is Majority Counting Algorithm.

public class Majority {

	public static int FindMostFrequentElement(int[] sequence)
	{
	    int best = 0; 
	    int count = 0;
	    for(int element:sequence)
	    {
	        if (count == 0)
	        {
	            best = element;
	            count = 1;
	        }
	        else
	        {
	            // Vote current choice up or down
	            count += (best == element) ? 1 : -1;
	        }
	    }
	    return best;
	}
	public static void main(String[] args) {
		int [] A = {7,11,8,11,11,9,11,7,11,8,11,9,11};
		System.out.println("Majority Element is"+FindMostFrequentElement(A));
	}
}