title: Determine if more than half the keys in an array of size n are the same key in O(n) time?
body: <p>You have an array or list of keys of known size n. It is unknown how many unique keys there are in this list, could be as little as 0 and up to and including n. The keys are in no particular order and they really can't be, as these keys have no concept of greater than or less than, only equality or inequality. Now before you say hash map, here's one more condition that I think throws a wrench in that idea: The value of each key is private. The only information you can get about the key is whether or not it is equal to another key. So basically:</p>
  
  <pre><code>class key{
      private:
          T data;
          ...
      public:
          ...
          bool operator==(const key &amp;k){return data==k.data}
          bool operator!=(const key &amp;k){return data!=k.data}
  };
  
  key array[n];
  </code></pre>
  
  <p>Now, is there an algorithm that can determine if more than half of the keys in the array are the same key in linear time? If not, what about O(n*log(n))? So for example say the array only has 3 unique keys. 60% of the array is populated with keys where key.data==foo, 30% key.data==bar and 10% key.data==derp. The algorithm only needs to determine that more than 50% of the keys are of the same kind (keys with data==foo) and also return one of those keys.</p>
  
  <p>According to my professor it can be done in O(n) time but he says we only have to find one that can do it in O(n*log(n)) time.</p>