Leetcode and Lintcode

Single number

Problem:

Given 2*n + 1 numbers, every numbers occurs twice except one, find it.

Have you met this question in a real interview? Yes
Example
Given [1,2,2,1,3,4,3], return 4

Challenge
One-pass, constant extra space.

Leetcode link
Lintcode link

Solution:

As we know, each two same integer after xor operation will lead to 0x00000000.
And if x is an integer, 0x00000000 ^ x = x.
So we can take the adantage of xor property to solve this problem.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*************************************************************************
    > File Name: SingleNumber.java
    > Author: Yao Zhang 
    > Mail: psyyz10@163.com 
    > Created Time: Sun 15 Nov 23:21:17 2015
 ************************************************************************/
                       
public class SingleNumber{
    public int singNumber(int[] A){
        if (A == null || A.length == 0){
            return 0; 
        }              
                       
        int result = A[0];
                       
        for (int i = 1; i < A.length; i++){                                                                                                                                          
            result = result ^ A[i];
        }              
                       
        return result;
    }                  
}