As a part of LeetCode's 30 Days 30 Challenges.

**Problem Statement**

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

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

**Possible Approaches for solving the given problem**

**Approach 1**

- Iterate over the given array. Add the element in the dictionary. Keep a check if the key already exists in the dictionary. Keep count of the element as the value. Then return the element(key) whose value(count) is 1.

**Problem with this approach**

- It'll iterate the complete list.
- Once the dictionary gets created. To return the element with count 1 again value corresponding to every element will have to be checked.
- Making the time complexity - O(n^2)
- This would also lead to runtime error.

**Approach 2**

- As the elements in the list are repeated. Convert the list into a set. A set consists of only unique elements.
- Instead of iterating over a complete list which would be complexity O(n). Iterate over the set i.e unique elements only.
- Iterate over the set and check the count of that element in the list. If count is 1. Return the element.

**Reasons this is better approach**

- We are not iterating over the complete array of duplicate elements unnecessarily hence making the solution efficient.
- Time Complexity - O(n). The complexity of the earlier solution was O(n^2).

```
class Solution:
def singleNumber(self, nums: List[int]) -> int:
unique_nums = set(nums)
for element in unique_nums:
count = nums.count(element)
if count == 1:
return element
```

**Learnings**

- Time complexity of set is O(1).
- Time complexity of list count is 0(n).
- Set consists of unique elements.

**Reference Links**

https://leetcode.com/explore/other/card/30-day-leetcoding-challenge/528/week-1/3283/

## Top comments (1)

You could also xor all the digits. The second occurrence cancels out the first.

No extra memory beyond a single int used.