Find the elements that appear only once

Question

The task:

Given an array of integers in which two elements appear exactly once and all other elements appear exactly twice, find the two elements that appear only once.

For example, given the array [2, 4, 6, 8, 10, 2, 6, 10], return 4 and 8. The order does not matter.

Follow-up: Can you do this in linear time and constant space?

const lst = [2, 4, 6, 8, 10, 2, 6, 10];

My functional solution

const findUnique = lst => lst
  .sort((a,b) => a - b)
  .filter((x, i) => lst[i-1] !== x && lst[i+1] !== x);

console.log(findUnique(lst));

My imperative solution:

function findUnique2(lst) {
  const res = [];
  const map = new Map();
  lst.forEach(x => map.set(x, map.get(x) === undefined));
  map.forEach((val, key) => {
    if(val) { res.push(key); }
  });
  return res;
}

console.log(findUnique2(lst));

I think the imperative solution is in linear time but not constant space. How would you do it with constant space?

Answer 1

How would you do it with constant space?

• Reduce the input list with ^, let's call this result xor
• xor is a ^ b, where a and b are the numbers that appear only once
• Any set bit appears in either a or b but not both
• Set bit to a single bit that is in xor. For example if xor is 6, then bit could be 2, or it could be 4, whichever, doesn't matter
• Filter the input list with & bit. Realize that the matched values will include either a or b but not both, thanks to our observation earlier. The filtered list will also include 0 or more duplicate pairs that may have matched.
• Reduce the filtered list with ^, let's call this result a. The value of b is xor ^ a.

Something like this:

function findUnique(lst) {
  const xor = lst.reduce((x, e) => x ^ e);
  var bit = 1;
  while ((bit & xor) === 0) {
    bit <<= 1;
  }
  const a = lst.filter(x => x & bit).reduce((x, e) => x ^ e);
  return [a, xor ^ a];

}

Answer 2

Sorting is not needed. A Set may be a better data structure for the task.

const find2Unique2 = a => Array.from( a.reduce( 
    (once, x) => (once.delete(x) || once.add(x), once),
    new Set() 
))

console.log( find2Unique2( [2, 0, 6, 8, 10, 2, 6, 10] ) );

I"m not sure how to solve this in constant space. If you xor all of the terms together

arr.reduce( (xor,x) => xor ^ x, 0 )

Then result = a ^ b, where a and b are your two unique terms. If you can figure out a, then b = result ^ a. Or you can find some other reduction, you'll have two equations and two unknowns, and an algebraic solution might be possible.

For example, xor of the negated array combines with positive xor to uniquely identify a and b if they are two bits wide:

  xor = arr.reduce( (xor,x) => xor ^ x, 0 )
  neg = arr.reduce( (xor,x) => xor ^ -x, 0 )

 a     b               xor   neg & 0xF (high bits omitted for clarity)
 0     1     =>          1  1111 
 0    10     =>         10  1110 
 0    11     =>         11  1101 
 1    10     =>         11     1 
 1    11     =>         10    10 
10    11     =>          1    11 

But it doesn't work for larger values. You could do multiple passes, with each pass xor-ing a right-shifted version of elements that could possibly match (if the last two bytes are 11 and 10, you can skip numbers that don't end in those bits).

I didn't implement this because it's pretty complicated and it doesn't seem like the right answer. But maybe it gives you an idea.