LeetCode 30day coding challenge #1

Single Number

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

---

This is the description written on the website, for more detail, look at this.

There are several methods to approach this problem. The first idea I thought of was to use the Counter function in python, which allows me to get a dictionary of the number of times each unique element appears in the list. So if I created a counter for the list [2,2,1], it should give me {2: 2; 1;1}. Since only one number appears once, I just need to extract the element that appeared once.

An implementation of this would look like this. We initiate a counter named x, and iterate through the list, We add all the numbers in the list into the Counter, and we return the number that only appeared once since the Counter keeps track of how many times each element appeared. However, this solution requires using negative slicing (the [-1:]) used to get the last element of the most common elements in the list, and unnecessary indices.

This solution isn't that pretty, right? Especially the part that requires using negative slicing. A prebuilt counter also probably don't exist in other programming languages. So I thought for a while and came up with another solution.

Now this solution is much more clean and elegant. The method used here is the bitwise XOR operator, which is the ^ symbol in the screenshot above. How XOR works is if we XOR the number 0 and some random bit, it will return that random bit. If we take the XOR of two same numbers, it will return 0. This means that since the question is asking us to return the one unique number, every other number that have even occurrences will become 0. We can simply iterate through the entire list and XOR all the bits together and get the answer.

That's it for question 1, and I'll see you in question 2

-Rex