question
Given an array filled with integers that appear exactly twice, with the exception
of one integer that appears once, find the unique integer.
ex. findUnique([1, 2, 6, 9, 9, 1, 3, 6, 2])
returns: 3
ex. findUnique([12, 45, 32, 65, 32, 65, 45])
returns: 12
ex. findUnique([1, 2, 6, 9, 9, 1, 3, 6, 2])
returns: 3
ex. findUnique([12, 45, 32, 65, 32, 65, 45])
returns: 12
The best solution for this will require using some bit-wise operators.
The optimal solution will run in O(n) and use O(1) space. Bitwise operators and
specifically the XOR operation will come in handy. Recall that any number XOR itself
will result in 0. Thus, by iterating through a given list and running the operation
on all of the numbers will result in just the unique number.
Check here for more information on the XOR operation.
findUnique(int input[])
int result = input[0];
for (int n = 1; n < input.size(); n++)
result ^= input[n];
// '^' is the XOR operator
return result;
Check here for more information on the XOR operation.