Find the elements that appear only once 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 =&gt; lst
  .sort((a,b) =&gt; a - b)
  .filter((x, i) =&gt; lst[i-1] !== x &amp;&amp; lst[i+1] !== x);

console.log(findUnique(lst));


My imperative solution:

function findUnique2(lst) {
  const res = [];
  const map = new Map();
  lst.forEach(x =&gt; map.set(x, map.get(x) === undefined));
  map.forEach((val, key) =&gt; {
    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?
Sorting is not needed.  A Set may be a better data structure for the task.



const find2Unique2 = a =&gt; Array.from( a.reduce( 
    (once, x) =&gt; (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) =&gt; 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) =&gt; xor ^ x, 0 )
  neg = arr.reduce( (xor,x) =&gt; xor ^ -x, 0 )

 a     b               xor   neg &amp; 0xF (high bits omitted for clarity)
 0     1     =&gt;          1  1111 
 0    10     =&gt;         10  1110 
 0    11     =&gt;         11  1101 
 1    10     =&gt;         11     1 
 1    11     =&gt;         10    10 
10    11     =&gt;          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.