# Find the elements that appear only once

Posted on

Problem

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?

Solution

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];

}
``````

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.