Easy

Given a non-empty 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?

Example 1:

1 | Input: [2,2,1] |

Example 2:

1 | Input: [4,1,2,1,2] |

## Solution

Actually it’s quite simple to solve, but we should make clear that it requires `O(N)`

complexity and no extra memory usage. So we need to find out the single one during several iterations.

As is well-known,

1 | a XOR a = 0 |

So all the duplicate numbers will be calculated to `0`

after looping xor, and the result of the iteration of xor must be the single number value.

Here is the sample code:

1 | class Solution: |

1 | public class SingleNumber { |

## Complexity Analysis

Time complexity of this approach is `O(N)`

;

Space complexity is `O(1)`

;

1 | Forgive my poor English, I just wanna improve my writing skill. |