LeetCode Single Number: Bit Operation

Overview

The key idea to solve the LeetCode Single Number problem is to use bit operation, the key idea is two facts: 1) A xor A = 0; 2) 0 xor A = A

LeetCode Single Number Problem

Given an array of integers, every element appears twice except for one. Find that single number.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Bit Operation and Solution

Basically, this is a simple question. There are three different kinds of approaches I can come up with (and note the without using extra memory actually means using constant memory, it is a bit misleading by this statement from LeetCode):

(1) Sort. Sort the array in O(NlogN) time and in one pass scan of the whole sorted array, we can identify the single number easily by identifying the single number which is not equal to either the previous one or the next number in the sorted array.

(2)  Hash. We hash each value in to buckets, and record the counting of each number, the single number which appears only once can be identified in linear time, however, this takes extra memory by the hashing nature.

(3) Bit operation. The bit operation ^ (xor) works like this: 1 ^ 1 = 0, 0 ^ 0 = 0, 1 ^ 0 = 1, 0 ^ 1 = 1, i.e., a ^ b = 0 if a == b while a ^ b == 1 if a != b where a and b are only one bit.  Then we know that  if two int number A and B, and we have A == B, then we have A ^ B == 0, and for any number C, we have the fact that C ^ 0 = C. As a result, we perform xor here for each number and the final result would be exactly the single number we want. This is because all the numbers which appear twice would be canceled after xor, which the canceled result is ZERO which however has no affects on the single number we want. The source code is quite simple as follows:

class Solution {
public:
    int singleNumber(int A[], int n) {
        int result = 0;
        for(int i = 0; i < n; ++i)
            result ^= A[i];
        return result;
    }
};

Summary

The key idea to solve the LeetCode Single Number problem is to use bit operation, the key idea is two facts: 1) A xor A = 0; 2) 0 xor A = A

Written on January 14, 2014