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.

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

[Thoughts]

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

[Solution]

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++)
            result^=A[i];
        return result;
    }
}

<< Back to Blog Discuss this post

 
Comments are closed.