---
# System prepended metadata

title: 'Single Number <img src="https://img.shields.io/badge/-easy-brightgreen">'
tags: [data_structure_python]

---

---
tags: data_structure_python
---

# Single Number <img src="https://img.shields.io/badge/-easy-brightgreen">

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

## Solution 1: Naive approach

```python=
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        dic = {}
        
        for elt in nums:
            if elt in dic:
                dic[elt] += 1
            else:
                dic[elt] = 1
        
        for elt in dic.keys():
            if dic[elt] == 1:
                return elt
```

## Solution 2: XOR gate approach

```python=
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        #O(n)
        res = 0        
        for elt in nums:
            res ^= elt
            
        return res
```
