Problem

Given an array of integers, in which all values occur an even number of times except for one which occurs an odd number of times. Find the integer that occurs an odd number of times.

For example, given this array: 4, 5, 7, 3, 4, 4, 4, 7, 3, 5, 7. The number 7 occurs an odd number of times while every other number occurs an even number of times, so the solution is 7.

Algorithm

My first thought when hearing this problem was to create an dictionary/hashmap to keep track of the count of each number and then just find the one with an odd count and return the corresponding number. This is a perfectly good solution that runs in O(n) time and also requires O(n) space (where n is the size of the array). O(n) is definitely the best we can do with time, because it would be impossible to solve the problem without looking at every number in the array, but we can do better with space using some bitwise operations!

Recall the bitwise XOR operator from boolean algebra. If you bitwise XOR a number with itself, you get 0. If you bitwise XOR a number with 0, you get the original number. If we XOR all the numbers in the array together, we are left with just the bits from the value that appears an odd number of times (since it didn't have a pair to cancel out with).

In our example:
4 XOR 5 = 1
1 XOR 7 = 6
6 XOR 3 = 5
5 XOR 4 = 1
1 XOR 4 = 5
5 XOR 4 = 1
1 XOR 7 = 6
6 XOR 3 = 5
5 XOR 5 = 0
0 XOR 7 = 7

As expected, the number we are left with is 7.

Here is the code in java:

public static int findOddSingleton(int[] nums) {
    int n = nums[0];
    for (int i = 1; i < nums.length; i++)
        n = n ^ nums[i];
    }
    return n;
}
Be Sociable, Share!