Bitwise Operations Changed My World: The Fascination of Algorithms

Table of Contents

Problem Solved
Lessons Learned
Supplement: What is a Hash Map?
Initial Solution
Answer
Reflections

Problem Solved

leetcode 136. Single Number
Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

Furthermore, the following conditions must be met:

• Linear runtime complexity $O(n)$
• Use only constant extra space $O(1)$

Lessons Learned

• Algorithms are definitely interesting!!!
• Hash maps are useful for counting and removing duplicates.
• When you want to reduce space complexity even further, take advantage of the problem's characteristics and use "bit manipulation."

Supplement: What is a Hash Map?

A data structure for quickly retrieving a value (value) for a given key (key).
It allows search, insertion, and deletion in $O(1)$ average time.

A Hash Map (HashMap):

1. Converts a key into a numeric value using a hash function (hash value)
2. Uses that hash value as an array index
3. Stores the value at the corresponding position

That is how it works.
That's why it's fast.

Think of it like converting a key (key) into a number and using that number as an address (array index) to leave a letter (value).
→ As long as you have the key, you can find the letter in one go.

In Python, this is implemented using the dict dictionary type. I'll omit the detailed implementation, but you can see an example of hash map usage below.

Initial Solution

Since I was asked to return the value that appears only once in nums, I thought I could use a hash map and tried to implement it.

first.py

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        hashmap = {}
        for i in nums:
            if i not in hashmap:
                hashmap[i] = 1
            else:
                hashmap[i] += 1
        filtered = [k for k, v in hashmap.items() if v == 1]
        return filtered[0]

Accepted on the first try! Yeeeeeeah!

However, the problem statement includes a condition to "make the space complexity $O(1)$." In first.py, the hash map grows in proportion to the number of input elements, resulting in $O(n)$, so it is not allowed.

That said, I couldn't immediately think of how to improve it, so I asked an AI for the answer.

Answer

The optimal solution for this problem is apparently an "O(n) time, O(1) space solution using XOR (exclusive OR)."

answer.py

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

Hmm, I don't quite get it. Let's look into it in detail.

What is XOR (Exclusive OR)?

It's an operation that results in 1 only when two bits are "different." In other words, it refers to an operation like the one shown below.

What is ^?

^ is one of the bitwise operators in Python that represents "exclusive OR."

It doesn't simply take the XOR of numbers; because it's a "bitwise operator," it converts the input to binary and then performs the XOR.

That's why you get a seemingly mysterious result like 1 ^ 5 → 4, but it makes sense when you look at the bitwise calculation in binary as shown below.

bit.py

1 ^ 5 # The answer is "4"

001 # "1" in binary
101 # "5" in binary
--- # XOR
100 # "4" in binary

Other bitwise operators are shown below:

What is result ^= n doing?

This is the same as result = result ^ n; it simply takes the XOR of result and the value from nums, then stores the outcome back into result.

In Python, ^ is the operator that represents exclusive OR.

While we are familiar with increments like a += 1, it's not common to see this used with XOR, so I didn't understand what was happening at first glance.

Conclusion

The key to this problem is that each number appears either once or twice.

This is because values that appear twice—meaning an even number of times—become exactly 0 when XORed.

bit_equ.py

101 # Decimal "5"
101 # Decimal "5"
--- # XOR
000 # Becomes "0"

A value that appears once—meaning an odd number of times—is never canceled out. Furthermore, since other values lose their influence as shown above, the mechanism is designed so that "if you keep XORing, only the value you finally want will emerge as the answer"!!

If you look at the intermediate calculations in decimal as shown below, it's hard to tell what's happening, but considering the binary calculation mentioned earlier, you'll see that you only need to focus on the output.

Reflections

Interesting!!!!
To think that mathematics can be so useful in a place like this.

I really like the feeling when knowledge from various fields comes together to finally lead to a result.
It's like independent pieces of knowledge in my head connect to become new knowledge, turning the known into the unknown, so to speak.

I feel this sensation particularly strongly in the AI field, so I want to keep enjoying it more.