---
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

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

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