Today I was Defeated by XOR

Today, I tackled a problem on LeetCode (I generally try to solve one daily, but to be entirely honest, I don't do it every day), and it dawned on me that I might have approached it incorrectly and didn't really know how to handle it. Let's start from the beginning, the task was “136. Single Number”.

How did I initially solve this task? I remembered that there was an efficient method called Counter, which creates a dictionary with unique elements from a given iterable sequence (like a list) as keys, and the count of their occurrences as values. Perfect, this means, considering the requirements of this task, somewhere in this dictionary returned by the Counter function there should be a key with the value 1, as all others should have 2 - as far as I understood. After a quick check on where to import Counter from, my solution was as follows

from collections import Counter
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return [k for k, v in Counter(nums).items() if v == 1][0]

As you can see, it's an implementation of singleNumber, where I thought, if I need to find that one specific key, I'll just do it in a list comprehension. It seemed the fastest way and since there should be only one value according to the task, but an int is expected, not a list, I returned the first element.

So good, I click "Run", the first 3 tests passed cool so I click "Submit" and everything there also green, so I was pleased with myself and checked off another task on LeetCode.

I took two sips of coffee and read the task again:

You must implement a solution with a linear runtime complexity and use only constant extra space.

You must implement a solution with a linear runtime complexity and use only constant extra space.

use only constant extra space. 

Well, maybe I did it wrong.

Memory Complexity:

1. Counter(nums) creates a new dictionary containing all unique elements from nums and their counts. The memory complexity depends on the number of unique elements in nums.
2. Creating a list in list comprehension also requires additional memory.

Therefore, this solution does not meet the requirement of using only constant additional memory (O(1)). Using Counter and creating a list in list comprehension increases the memory complexity to O(n) or more, depending on the number of unique elements in nums.

I admit, I didn't come up with the solution myself; I saw a hint - XOR 
But even that didn't help me, I only remembered classes from my first year of university in C++ programming, where we did bit operations, one of which was XOR, and I remembered that we used Boolean algebra, where XOR was also present.
But how is this going to help me solve this task - I HAVE NO FUCKING IDEA
So, I saw the solution:

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        result = 0
        for num in nums:
            result ^= num
        return result

And still, I don't get how this piece of code tells me which value in the `nums` array appears only once. I start questioning what I am doing in front of the monitor, writing some code, working on projects, learning server administration, or anything related to the binary world if I am not able to understand why these 4 lines of code solve the problem.

Let's start from the basics.

The XOR operation, also known as "exclusive or", is one of the fundamental bit operations. In the context of bit operations, XOR compares the bits of two numbers and returns 1 only when the bits differ - hence the name "exclusive or". Here's how it works at the bit level:

As you can see, the result is 1 only when the bits are different.

In Python, the XOR operation is represented by the symbol `^`. Let's look at some examples:

• 3 ^ 3` equals 0, because binary 3 is 011, and the XOR operation of the same number always yields 0.
• 3 ^ 2` equals 1, because binary 3 is 011 and 2 is 010. Only one bit is different (the least significant bit), so the result is 001, which is 1 in decimal.

If someone still doesn't get it, let's break down the second point:

In this table:

• The first column shows the bits of number 3 (011).
• The second column shows the bits of number 2 (010).
• The third column shows the result of the XOR operation on each bit.

The XOR operation returns 1 only when the bits are different. In this case, only the last bit (least significant) is different between the numbers 3 and 2. Therefore, the XOR result of these two numbers is 001, which in the decimal system is 1.

In the context of our problem, the XOR operation is used to find the unique element in an array where every other element appears twice. This happens because any element that appears twice will be reduced to 0 after applying the XOR operation

The XOR operation (exclusive or) has several unique properties that make it ideal for solving the problem of finding a unique element in an array where every other element appears twice. Here are the key properties:

1. Idempotence: The XOR operation of any number with itself always results in 0.

2. Behavior with Zero: XORing any number with 0 yields the same number.

3. Commutativity and Associativity: The XOR operation is commutative and associative, which means the order of operations doesn't matter, and the result remains the same.

In the context of the problem:

• If we have an array where every element except one appears exactly twice, performing the XOR operation on each element will cause all elements that appear twice to "cancel out" each other to 0 (due to idempotence).
• Consequently, the only element that does not have a pair remains unchanged, because XORing any number with 0 yields the same number.

That's all for today.