# LeetCode 136 Single Number (Python)

## Description

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:

``````Input: [2,2,1]
Output: 1
``````

Example 2:

``````Input: [4,1,2,1,2]
Output: 4
``````

## Solution:

https://github.com/younglaker/leetcode/blob/master/38_Count_and_Say.py

### Approach 1 - Array

Use array(in Python called list) to store numbers in nums. If some number in `nums` is new to array, append it.If some number is already in the array, remove it

• Time complexity : O(n^2). `for i in nums` takes O(n) time, and `if i in list` is also a for-loop taking O(n) time.
• Space complexity : O(n). We need a list of size n to contain elements in nums.

### Approach 2 - Hash

or:

Use array(in Python called list) to store numbers in nums. If some number in `nums` is new to array, append it.If some number is already in the array, remove it

• Time complexity : O(n). `for i in nums` takes O(n) time, and `if dict.has_key(i)` takes O(1) time.
• Space complexity : O(n). We need a hash table of size n to contain elements in nums.

### Approach 3: Math

2∗(a+b+c)−(2a+2b+c)=c

• Time complexity : O(n + n) = O(2n)=O(n). `sum()` is a for-loop.
• Space complexity : O(n + n) = O(2n)=O(n). A set needs space for the elements in nums

### Approach 4: XOR

Because `a⊕0=a` and `a⊕a=0`
Then: `a⊕b⊕a=(a⊕a)⊕b=0⊕b=b`
So we can XOR all bits together to find the unique number.

Exchange blogroll： http://laker.me/blog
Github：https://github.com/younglaker

LeetCode 136 Single Number (Python) 