How to find a single number in an array that does not occur twice

Question

The following is taken from the interview:

In this array, which contains integers, each number is repeated once, with the exception of one that is not repeated. Write a function that finds a number that does not repeat.

I was thinking about using a HashSet, but that could complicate things ...

Any ideas for a simple solution?

Answer 1

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

At the end, the “result” will be equal to the only element that appears only once.

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

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

For example, if your array contains 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 also be 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

Answer 2

I have already seen this question. This is a trick. Assuming all duplicate numbers are displayed exactly twice, you do this:

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

Answer 3

Another “normal” 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 looks beautiful.

It's not as fast as XOR, but using a HashSet makes it close to O (n). And it is certainly more readable.

Answer 4

The best answer has already been given (XOR-ing), this will be an alternative, more general way.

If the input array is sorted (we can sort it), we could just iterate over the elements in pairs (step by step 2), and if the elements of the “pair” are different, we do the following:

 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 undesirable or not permitted, it may be cloned first:

 arr = arr.clone(); 

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

Generalization

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

Here is a slightly modified version that takes an input array of any type of element that 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 can also use arr[i].equals(arr[i + 1]) to compare items instead of Comparable.compareTo() . Read the related javadoc for details. Quoting the relevant part:

It is highly recommended, but not necessary, 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. Recommended language: "Note: this class has a natural order that is incompatible with peers."

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

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

Output:

 2 

Concluding remarks:

Starting with the problem statement, it does not check if there are more than two occurrences of elements, and if the length of the array is odd. In addition, the second example does not check for null values; they should be added if necessary.

Answer 5

Here's a slightly less confusing way to do this:

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

result will contain a non-duplicate value.