title: Determining if an array has a k-majority element
body: <p>Suppose that, given an n-element multiset A (not sorted), we
  want an O(n) time algorithm for determining whether A contains a majority element, i.e.,
  an element that occurs more than n/2 times in A. It is easy to solve this in O(n) time by
  using the linear-time selection algorithm by ﬁnding the median (call it x), then counting
  how many times x occurs in A and returning it as the majority if the count exceeds n/2
  (otherwise the answer is “there is no majority”). Now consider the following generalization
  of the problem: Given A and an integer k &lt; n, we want an algorithm that determines
  whether A contains a value that occurs more than n/k times in it (if many such values
  exist, then it is enough to ﬁnd one of them). Design an algorithm for doing this, and
  analyze its complexity as a function of n and k. Your grade on this question will depend on
  how fast your algorithm is (of course it also has to be correct). Partial credit of 10 points is given for an O(kn) time algorithm, full credit is for an O(n log k) time algorithm.</p>
  
  <p>now I have come up with 2 solutions for the problem but neither fully satisfy the 
  O(n log k) requirement.  immediately i saw that i could sort the array using a O(n log n) algorithm then go through and see if any elements repeat more than n/k times linearly but that is O(n log n) not O(n log k)</p>
  
  <p>I also have found and somewhat understood a O(nk) methood done by making an array of the same data type as the input and an int that is k long. then putting each element into an empty element incrementing its counter or if it matches one element in there incrementing its counter till we reach the k+1th unique element at which point you decrement all the counters by 1 till one reaches 0 at which point it is considered empty and the new element can be placed in it. and so on till the end of the input array. then checking all the elements left after we are done to see if they occur more than n/k times.  but since this involves checking the n original elements against all k of the new arrays elements it is O(nk).  any hints on how to do this problem in O(n log k)? I think the O(nk) algorithm is along the lines of how he wants us to think but I'm not sure where to go from here.</p>