title: Find the k non-repeating elements in a list with "little" additional space
body: <p>The original problem statement is this one:</p>
  
  <blockquote>
    <p>Given an array of 32bit unsigned integers in which every number appears exactly twice except three of them (which appear exactly once), find those three numbers in O(n) time using O(1) extra space. The input array is read-only. What if there are k exceptions instead of 3?</p>
  </blockquote>
  
  <p>It's easy to solve this in <code>Ο(1)</code> time and <code>Ο(1)</code> space if you accept a very high constant factor because of the input restriction (the array can have at most 2<sup>33</sup> entries):</p>
  
  <pre class="lang-python prettyprint-override"><code>for i in lst:
      if sum(1 for j in lst if i == j) == 1:
          print i
  </code></pre>
  
  <p>So, for the sake of this question, <strong>let's drop the restriction in bit length and concentrate on the more general problem where the numbers can have up to <code>m</code> bits.</strong></p>
  
  <p><a href="http://www.geeksforgeeks.org/archives/2457" rel="noreferrer">Generalizing an algorithm for k = 2</a>, what I had in mind is the following:</p>
  
  <ol>
  <li>XOR those numbers with a least significant bit of <code>1</code> and those with a <code>0</code> separately. If for both of the partitions, the resulting value is not zero, we know that we have partitioned the non-repeating numbers into two groups, each of which has at least one member</li>
  <li>For each of those groups, try to partition it further by examining the second-least significant bit and so on</li>
  </ol>
  
  <p>There is a special case to be considered, though. If after partitioning a group, the XOR values of one of the groups are both zero, we don't know whether one of the resulting sub-groups is empty or not. In this case my algorithm just leaves this bit out and continues with the next one, which is incorrect, for example it fails for the input <code>[0,1,2,3,4,5,6]</code>.</p>
  
  <p>Now the idea I had was to compute not only the XOR of the element, but also the XOR of the values after applying a certain function (I had chosen <code>f(x) = 3x + 1</code> here). See Evgeny's answer below for a counter-example for this additional check.</p>
  
  <p>Now although <strong>the below algorithm is not correct for k >= 7</strong>, I still include the implementation here to give you an idea:</p>
  
  <pre class="lang-python prettyprint-override"><code>def xor(seq):
    return reduce(lambda x, y: x ^ y, seq, 0)
  
  def compute_xors(ary, mask, bits):
    a = xor(i for i in ary if i &amp; mask == bits)
    b = xor(i * 3 + 1 for i in ary if i &amp; mask == bits)
    return a if max(a, b) &gt; 0 else None
  
  def solve(ary, high = 0, mask = 0, bits = 0, old_xor = 0):
    for h in xrange(high, 32):
      hibit = 1 &lt;&lt; h
      m = mask | hibit
      # partition the array into two groups
      x = compute_xors(ary, m, bits | hibit)
      y = compute_xors(ary, m, bits)
      if x is None or y is None:
        # at this point, we can't be sure if both groups are non-empty,
        # so we check the next bit
        continue
      mask |= hibit
      # we recurse if we are absolutely sure that we can find at least one
      # new value in both branches. This means that the number of recursions
      # is linear in k, rather then exponential.
      solve(ary, h + 1, mask, bits | hibit, x)
      solve(ary, h + 1, mask, bits, y)
      break
    else:
      # we couldn't find a partitioning bit, so we output (but 
      # this might be incorrect, see above!)
      print old_xor
  
  # expects input of the form "10 1 1 2 3 4 2 5 6 7 10"
  ary = map(int, raw_input().split())
  solve(ary, old_xor=xor(ary))
  </code></pre>
  
  <p>From my analysis, this code has a worst-case time complexity of <code>O(k * m² * n)</code> where <code>n</code> is the number of input elements (XORing is <code>O(m)</code> and at most <code>k</code> partitioning operations can be successful) and space complexity <code>O(m²)</code> (because <code>m</code> is the maximum recursion depth and the temporary numbers can be of length <code>m</code>).</p>
  
  <p>The question is of course if there is a <em>correct</em>, efficient approach with good asymptotic runtime (let's assume that <code>k &lt;&lt; n</code> and <code>m &lt;&lt; n</code> here for the sake of completeness), which also needs little additional space (for example, approaches that sort the input will not be accepted, because we'd need at least <code>O(n)</code> additional space for that, as we can't modify the input!).</p>
  
  <p><strong>EDIT:</strong> Now that the algorithm above is proven to be incorrect, it would of course be nice to see how it could be made correct, possibly by making it a bit less effient. Space complexity should be in <code>o(n*m)</code> (that is, sublinear in the total number of input bits). It would be okay to take <code>k</code> as an additional input if that makes the task easier.</p>