Find a unique integer in an array

There is a standard algorithm to solve such problems using XOR operator:

Time Complexity = O(n)

Space Complexity = O(1)

Suppose your input array contains only one element that occurs odd no of times and rest occur even number of times,we take advantage of the following fact:

Any expression having even number of 0's and 1's in any order will always be = 0 when xor is applied.

That is

0^1^....... = 0 as long as number of 0 is even and number of 1 is even 

and 0 and 1 can occur in any order.

Because all numbers that occur even number of times will have their corresponding bits form even number of 1's and 0's and only the number which occurs only once will have its bit left out when we take xor of all elements of array because

0(from no's occuring even times)^1(from no occuring once) = 1 

0(from no's occuring even times)^0(from no occuring once) = 0

as you can see the bit of only the number occuring once is preserved.

This means when given such an array and you take xor of all the elements,the result is the number which occurs only once.

So the algorithm for array of length n is:

 result = array[0]^array[1]^.....array[n-1] 

Different Scenario

As the OP mentioned that input can also be an array which has two numbers occuring only once and rest occur even number of times.

This is solved using the same logic as above but with little difference.

Idea of algorithm:

If you take xor of all the elements then definitely all the bits of elements occuring even number of times will result in 0,which means:

The result will have its bit 1 only at that bit position where the bits of the two numbers occuring only once differ.

We will use the above idea.

Now we focus on the resultant xor bit which is 1(any bit which is 1) and make rest 0.The result is a number which will allow us to differentiate between the two numbers(the required ones).

Because the bit is 1,it means they differ at this position,it means one will have 0 at this position and one will have 1.This means one number when taken AND results in 0 and one does not.

Since it is very easy to set the right most bit,we set it of the result xor as

 A = result & ~(result-1)

Now traverse through the array once and if array[i]&A is 0 store the number in variable number_1 as

 number_1 = number_1^array[i]

otherwise

 number_2 = number_2^array[i]

Because the remaining numbers occur even number of times,their bit will automatically disappear.

So the algorithm is

1.Take xor of all elements,call it xor.

2.Set the rightmost bit of xor and store it in B.

3.Do the following:

number_1=0,number_2=0;
for(i = 0 to n-1)
{
 if(array[i] & B)
  number_1 = number_1^array[i];
 else
  number_2 = number_2^array[i];
}

The number_1 and number_2 are the required numbers.

The question title says "the unique integer", but the question body says there can be more than one unique element.

If there is in fact only one non-duplicate: XOR all the elements together. The duplicates all cancel, because they come in pairs (or higher multiples of 2), so the result is the unique integer.

See Dante's answer for an extension of this idea that can handle two unique elements. It can't be generalized to more than that.

Perhaps for k unique elements, we could use k accumulators to track sum(a[i]**k). i.e. a[i], a[i]², etc. This probably only works for Faster algorithm to find unique element between two arrays?, not this case where the duplicates are all in one array. IDK if an xor of squares, cubes, etc. would be any use for resolving things.

Track the counts for each element and only return the elements with a count of 1. This can be done with a hash map. The below example tracks the result using a hash set while it's still building the counts map. Still O(n) but less efficient, but I think it's slightly more instructive.

Javascript with jsfiddle http://jsfiddle.net/nmckchsa/

function findUnique(arr) {
    var uniq = new Map();
    var result = new Set();
    // iterate through array
    for(var i=0; i<arr.length; i++) {
        var v = arr[i];
        // add value to map that contains counts
        if(uniq.has(v)) {
            uniq.set(v, uniq.get(v) + 1);
            // count is greater than 1 remove from set
            result.delete(v);
        } else {
            uniq.set(v, 1);
            // add a possibly uniq value to the set
            result.add(v);
        }
    }
    // set to array O(n)
    var a = [], x = 0;
    result.forEach(function(v) { a[x++] = v; });
    return a;
}
alert(findUnique([1,2,3,0,1,2,3,1,2,3,5,4,4]));

EDIT Since the non-uniq numbers appear an even number of times @PeterCordes suggested a more elegant set toggle.

Here's how that would look.

function findUnique(arr) {
    var result = new Set();
    // iterate through array
    for(var i=0; i<arr.length; i++) {
        var v = arr[i];
        if(result.has(v)) { // even occurances
            result.delete(v);
        } else { // odd occurances
            result.add(v);
        }
    }
    // set to array O(n)
    var a = [], x = 0;
    result.forEach(function(v) { a[x++] = v; });
    return a;
}

JSFiddle http://jsfiddle.net/hepsyqyw/

Assuming you have an input array: [2,3,4,2,4] Output: 3

In Ruby, you can do something as simple as this:

[2,3,4,2,4].inject(0) {|xor, v| xor ^ v}