You have an array of N bit strings each of length M. You know that there is at least one element that appears more than N/8 times in the array. Using O(M+log(N)) memory and O(NM) time, find such an element.

An Easier Version

Well, its actually almost exactly the same, but solve the above riddle in case there is an element that appears more than N/2 times in the array. I managed to find 3 distinct solutions to this easier variation, but only one of which generalizes easily.

Thanks Nemo for giving me this riddle!

Spoiler Alert - Solution Ahead!

The solution’s central idea is that if you discard any k distinct elements of the array (k = 8 in the original version, or k = 2 in the easier version) an element that appeared more than \(\frac{1}{k}\) before discarding, will continue to appear more than \(\frac{1}{k}\) after discarding (note that this is a one way implication, i.e. it is possible for an element to appear more than \(\frac{1}{k}\) after discarding but not before). We therefore keep an auxiliary array S of size 7 (k-1) of bit strings and integer counts. We reset all the counts to 0. We then iterate through our original array and for each element:

• If it is already in the S array, we increment its count.
• Otherwise, if there is room in the S array (i.e. there is an element with a count of 0), we add it to the S array (and set its count to 1).
• Otherwise, we subtract 1 from all elements in the S array (which is akin to discarding 8 distinct elements).

We end up with 7 elements, one of which appears more than \(\frac{1}{8}\) in the original array, but since the implication is one-directional we need one final pass to count for each candidate how often is appears in the original array.

Here it is in Python:

def better_half(A, N = 8):
  S = [[None, 0] * (N - 1)]
  for x in A:
    for s in S:
      if x == s[0]:
        s[1] += 1
        break
    else:
      for s in S:
        if s[1] == 0:
          s[0] = x
          s[1] = 1
          break
      else:
        for s in S:
          s[1] -= 1
  for s in S:
    if s[1] != 0:
      if A.count(S) > len(A) // N:
        return s[0]