Our blog, keeping you up-to-date on our latest news.


[Leetcode]Single Number

January 29, 2015 at 5:51 am | Algorithms | No comment


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

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


So this is a good example of algorithm that uses bit-wise operation.

As each number appears twice except for one, so if we can make all pairs disappear, then the remaining one will be  the single one. And the bit-wise operator XOR is just the operator we needed, as it has this nature:

x ^ 0 == x
x ^ x == 0


public class Solution {
    public int singleNumber(int[] A) {
        if(A == null || A.length == 0)
            return 0;
        int result = A[0];
        for(int i = 1; i<A.length; i++)
        return result;

<< Back to Blog Discuss this post

Comments are closed.