title: Most common element in an array / Finding the relative majority, deterministically in O(n) time and O(1) space?
body: <p>So for example, the answer for the array:</p>
  
  <p>1, 11, 3, 95, 23, 8, 1</p>
  
  <p>would be 1, since all the other elements only occur once while 1 occurs twice. </p>
  
  <p>A lot of the questions similar to this question that I've seen on stackoverflow ask to find the absolute majority (the answer occurs at least n/2 in an array of length n), or answer the question using sorting or a hash table. The former is not what I'm asking, and the latter is either too slow ( O(n log n) for sorting ) or uses too much memory ( O(n) for a hash table ).</p>
  
  <p>Does such an algorithm exist? If not, is there a proof showing why it's impossible? Including a source would be nice.</p>