LeetCode: Single Number

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

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

---

We can use the binary operation xor to find out the single number. Since a xor a = 0 and 0 xor 0 = 0 and 0 xor 1 = 1.

C++ Code:

/*
 * func: single_number
 * goal: find the single number in an array that occurs once
 * @param A: input array A
 * @param n: size of the array
 * return: the single number
 */
int single_number(int A[], int n){
    if(n <= 0){
        return 0;
    }
    int num = A[0];
    for(int i=1; i<n; ++i){
        num ^= A[i];
    }
    return num;
}

Python Code:

# func: find the single number in a list
# @param A: input list
# @return: single number
def single_numer(A):
    if not A:
        return 0
    result = A[0]
    for i in xrange(1, len(A)):
        result ^= A[i]

    return result