Question

link

Stats

Adjusted Difficulty	4
Time to use	--------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

First solutions is bit manipulation.

If two numbers are the same, then XOR result is 0.

And for negative integers:

A negative number is a bit field just like a positive number. XOR doesn’t care

Follow-up question, what if the input is not an array in interger, but a bunch of Strings? This guy have the answer.

There are ways of XORing strings by XORing the individual chars - you would just have to have a temporary variable as large as the largest string.

What wouldn’t work is trying to XOR a linked list or some other complicated data structure.

Which is to say, a string is just like an array of chars (integers). For every char (integer), just apply the same method and we shall have the answer.

Second solution is HashSet, but must use more space. Code is posted below as well.

Someone also sort then find, but this takes more time.

Code

First, XOR solution

public int singleNumber(int[] A) {
    int num = A[0];
    for (int i = 1; i < A.length; i ++)
        num = num ^ A[i];
    return num;
}

Second, HashSet solution

The last line “return -1” is only for compiling purposes, and will not be executed.

public int singleNumber(int[] A) {
    HashSet<Integer> set = new HashSet<Integer>();
    for (int i = 0; i < A.length; i ++) {
        if (set.contains(A[i]))
            set.remove(A[i]);
        else
            set.add(A[i]);
    }
    for (Integer a: set)
        return a;
    return -1;
}