首页 > itarticle > single number

single number

admin 11月 11, 2020 0

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.


    > File Name: SingleNumber.java
    > Author: Yao Zhang 
    > Mail: [email protected] 
    > Created Time: Sun 15 Nov 23:21:17 2015
 ************************************************************************/
                       
public class {
    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;
    }                  
}