136 Single Number – Medium
Problem:
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:
This is surely a tricky question. It’s good to know how to solve. But I don’t think this is a good interview question, namely not a good question to measure a programmer’s problem solving skills.
Start with value 0, if there are two same number, when you do a XOR, you flip the bit twice which means the bit will remain 0. but for the unique number, the corresponding bit only flipped once, 0 -> 1, so the value will end up as the unique number.
Solutions:
public class Solution {
public int singleNumber(int[] A) {
int result = 0;
for (int i = 0; i < A.length; i ++)
result = result ^ A[i];
return result;
}
}