How to find the only number in an array that doesn't occur twice [duplicate]

57
votes

The following is taken from a job interview:

In a given array, which contains integers, each number repeats itself once except for one, which doesn't repeat. Write a function that finds the number that doesn't repeat.

I thought about using an HashSet, but it might complicate everything...

Any ideas of a simple solution?

5
javaarraysalgorithm
Are there any constraints you have to work within? – Duncan Jones
stackoverflow.com/q/35185/1402846, stackoverflow.com/q/1089987/1402846, stackoverflow.com/q/2644179/1402846 – Pang
If I'm the interviewer, @Thomas answer will not satisfy me. I want clean, readable code, not short code which nobody understands. This means you'd need to write comments about what it does and clearly explain the limitations, e.g. this approach does not work if an item occurs more than 2 times. Next, provide some unit tests. Otherwise you get best answers on codegolf.SE – Thomas Weller
If I were the interviewer, it would be exactly what I asked for. It's a mean interview question. The interviewer just wanted to see if you know the same trick he does. – Dennis_E
If @Thomas' answer is what they are looking for, it's a lousy interview question. Trivia is about the worst way to determine if someone is a good programmer. I'd be wary of that organization. – Necreaux

5 Answers

142
votes

You can define an integer "result" initialized to 0, and then you do some bitwise operations by applying a XOR logic to all elements in your array.

At the end, "result" will be equal to the only element that appears only one time.

result = 0
for i in array:
  result ^= i
return result

http://en.wikipedia.org/wiki/Bitwise_operation#XOR

For instance, if your array contains the elements [3, 4, 5, 3, 4], the algorithm will return

3 ^ 4 ^ 5 ^ 3 ^ 4

But the XOR operator ^ is associative and commutative, so the result will be also equal to:

(3 ^ 3) ^ (4 ^ 4) ^ 5

Since i ^ i = 0 for any integer i, and i ^ 0 = i, you have

(3 ^ 3) ^ (4 ^ 4) ^ 5 = 0 ^ 0 ^ 5 = 5

20
votes

I've seen this question before. It's a trick. Assuming all the repeated numbers appear exactly twice you do this:

int result = 0;
for (int a : arr)
    result ^= a;
14
votes

Yet another "ordinary" solution (in Java):

public static int findSingle(int[] array) {

    Set<Integer> set = new HashSet<Integer>();

    for (int item : array) {
        if (!set.remove(item)) {
            set.add(item);
        }
    }       

    assert set.size() == 1;

    return set.iterator().next();
}

In my opinion the solution with XOR is kind of beautiful.

This one is not as fast as XOR but usage of HashSet makes it close to O(n). And it is certainly more readable.

5
votes

The best answer is already given (XOR-ing the elements), this is to provide an alternative, more general way.

If the input array would be sorted (we can make it sorted), we could simply iterate over the elements in pairs (stepping by 2) and if the elements of the "pair" are different, we're done:

public static int findSingle(int[] arr) {
    Arrays.sort(arr);
    for (int i = 0, max = arr.length - 1; i < max; i += 2)
        if (arr[i] != arr[i + 1])
            return arr[i];
    return arr[arr.length - 1]; // Single element is the last
}

Note: This solution sorts the input array; if this is unwanted or not allowed, it can be cloned first:

arr = arr.clone();

If input array is sorted, the Arrays.sort(arr) call can be left out of course.

Generalization

The advantage of this solution is that it can be applied to all types which are comparable and therefore can be sorted (types which implement Comparable), for example String or Date. The XOR solution is limited to numbers only.

Here is a slightly modified version which takes an input array of any element type which is comparable:

public static <E extends Comparable<E>> E findSingle(E[] arr) {
    Arrays.sort(arr);
    for (int i = 0, max = arr.length - 1; i < max; i += 2)
        if (arr[i].compareTo(arr[i + 1]) != 0)
            return arr[i];
    return arr[arr.length - 1]; // Single element is the last
}

Note: In most cases you could also use arr[i].equals(arr[i + 1]) to compare elements instead of using Comparable.compareTo(). For details read the linked javadoc. Quoting the relevant part:

It is strongly recommended, but not strictly required that (x.compareTo(y)==0) == (x.equals(y)). Generally speaking, any class that implements the Comparable interface and violates this condition should clearly indicate this fact. The recommended language is "Note: this class has a natural ordering that is inconsistent with equals."

Now you can call this with a String[] for example:

System.out.println(findSingle(new String[] { "1", "2", "3", "1", "3" }));

Output:

2

Final notes:

Starting from the problem statement it is not checked whether there are more than 2 occurrences of the elements, and neither is whether the array length is odd. Also the second example doesn't check for null values, these are to be added if necessary.

2
votes

Here's a slightly less obfuscated way to do it:

List list = Arrays.asList(a);
int result;
for(int i:a)
{
    if(list.indexOf(i)==list.lastIndexOf(i))
    {
        result = i;
        break;
    }
}

result will contain the non-repeated value.