Question: A majority element in an array A of size N is an element that appears more than times (thus there is at most one such element).
For example, the array
3, 3, 4, 2, 4, 4, 2, 4, 4
has a majority element (4), whereas the array
3, 3, 4, 2, 4, 4, 2, 4
does not. Give an algorithm to find a majority element if one exists, or reports that one does not. What is the running time of your algorithm?