Problem Description

You are given an array nums where each number appears either once or twice.

Your task is to find the bitwise XOR of all numbers that appear exactly twice in the array. If no number appears twice, return 0.

For example:

• If nums = [1, 2, 3, 2, 4], the number 2 appears twice, so the result would be 2
• If nums = [1, 2, 1, 3, 2], both 1 and 2 appear twice, so the result would be 1 XOR 2 = 3
• If nums = [1, 2, 3], no number appears twice, so the result would be 0

The solution uses a Counter to track the frequency of each number, then filters for numbers with a count of exactly 2, and applies XOR operation on all such numbers using reduce.

Intuition

The key insight is that we need to identify which numbers appear exactly twice and then combine them using XOR operation.

Why XOR? The XOR operation has useful properties for this problem:

• a XOR 0 = a (identity property)
• a XOR b XOR c = (a XOR b) XOR c (associative property)
• The order of XOR operations doesn't matter

To solve this problem, we need two steps:

1. Count occurrences: We need to know which numbers appear twice. A frequency counter or hash table is perfect for this - it lets us track how many times each number appears in the array.

2. Combine duplicates: Once we know which numbers appear twice, we XOR them together. Starting with 0 as our initial value ensures that if no numbers appear twice, we return 0 (since 0 XOR nothing = 0).

The beauty of this approach is its simplicity - we make one pass to count frequencies, then filter for numbers with count 2, and apply XOR to get our answer. The reduce function with xor elegantly handles the accumulation of XOR operations across all duplicate numbers.

Solution Approach

The solution follows a counting-based approach to identify and process duplicate numbers:

1. Count Occurrences: We use Python's Counter from the collections module to create a frequency map. The Counter(nums) creates a dictionary-like object where:

   • Keys are the unique numbers from the array
   • Values are their occurrence counts

2. Filter Duplicates: We iterate through the counter's items using cnt.items(), which gives us (number, count) pairs. We filter for numbers where the count equals 2 using a list comprehension: [x for x, v in cnt.items() if v == 2]

3. Apply XOR Operation: We use reduce with the xor operator to combine all duplicate numbers:

   • reduce(xor, filtered_list, 0) starts with initial value 0
   • It applies XOR operation sequentially: 0 XOR first_duplicate XOR second_duplicate XOR ...
   • If the filtered list is empty (no duplicates), it returns the initial value 0

Example walkthrough:

• For nums = [4, 3, 2, 3, 1, 2]:
  • Counter creates: {4: 1, 3: 2, 2: 2, 1: 1}
  • Filter duplicates: [3, 2] (numbers with count = 2)
  • Apply XOR: 0 XOR 3 XOR 2 = 3 XOR 2 = 1

The time complexity is O(n) where n is the length of the array (one pass for counting), and space complexity is O(k) where k is the number of unique elements in the array.

Example Walkthrough

Let's walk through the solution with nums = [5, 3, 5, 7, 3, 9]:

Step 1: Count Occurrences Using Counter(nums), we create a frequency map:

• 5 appears 2 times
• 3 appears 2 times
• 7 appears 1 time
• 9 appears 1 time

Result: {5: 2, 3: 2, 7: 1, 9: 1}

Step 2: Filter for Duplicates We iterate through the counter and keep only numbers with count = 2:

• 5 has count 2 ✓ (include)
• 3 has count 2 ✓ (include)
• 7 has count 1 ✗ (exclude)
• 9 has count 1 ✗ (exclude)

Filtered list: [5, 3]

Step 3: Apply XOR Operation Using reduce(xor, [5, 3], 0):

• Start with initial value: 0
• First operation: 0 XOR 5 = 5
• Second operation: 5 XOR 3 = 6

Let's verify the XOR calculation in binary:

• 5 in binary: 101
• 3 in binary: 011
• 5 XOR 3: 110 = 6 in decimal

Final Result: 6

This represents the XOR of all numbers that appear exactly twice in the array.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. This is because:

• Creating the Counter requires iterating through all n elements once: O(n)
• Iterating through the Counter items (at most n distinct elements) and filtering those with count equal to 2: O(n) in the worst case
• The reduce operation with XOR on the filtered elements: O(k) where k ≤ n is the number of elements that appear exactly twice

The overall time complexity is O(n) + O(n) + O(k) = O(n).

The space complexity is O(M), where M is the number of distinct elements in the array nums. This is because:

• The Counter dictionary stores each distinct element as a key with its frequency as the value, requiring O(M) space
• The list comprehension creates a temporary list of elements that appear exactly twice, which in the worst case could be O(M) if all distinct elements appear exactly twice
• The reduce operation uses O(1) additional space

Therefore, the dominant space complexity is O(M), where M ≤ n represents the number of distinct elements in nums.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the XOR Identity Property

A common mistake is not recognizing that XOR with 0 is an identity operation (x XOR 0 = x). Some developers might try to handle the empty list case separately:

Incorrect approach:

def duplicateNumbersXOR(self, nums: List[int]) -> int:
    frequency_map = Counter(nums)
    duplicate_numbers = [num for num, count in frequency_map.items() if count == 2]
  
    # Unnecessary special case handling
    if not duplicate_numbers:
        return 0
  
    result = duplicate_numbers[0]
    for i in range(1, len(duplicate_numbers)):
        result ^= duplicate_numbers[i]
    return result

Why it's a pitfall: The reduce(xor, duplicate_numbers, 0) already handles the empty list case elegantly by returning the initial value 0.

2. XORing the Wrong Values

Some might accidentally XOR the counts instead of the numbers themselves, or XOR each duplicate twice:

Incorrect approach:

def duplicateNumbersXOR(self, nums: List[int]) -> int:
    result = 0
    for num in nums:
        if nums.count(num) == 2:
            result ^= num  # Wrong: XORs each duplicate twice!
    return result

Why it's a pitfall: If a number appears twice in the array, this approach would XOR it twice (once for each occurrence), which would cancel out to 0 due to XOR's self-inverse property (x XOR x = 0).

3. Inefficient Counting Methods

Using nested loops or repeatedly calling count() instead of using Counter:

Inefficient approach:

def duplicateNumbersXOR(self, nums: List[int]) -> int:
    seen = set()
    result = 0
    for num in nums:
        if num not in seen and nums.count(num) == 2:  # O(n) operation inside loop!
            result ^= num
            seen.add(num)
    return result

Why it's a pitfall: This creates O(n²) time complexity because nums.count(num) is O(n) and it's called inside an O(n) loop.

4. Forgetting Edge Cases

Not considering that the problem specifically asks for numbers appearing exactly twice, not "at least" twice:

Incorrect interpretation:

def duplicateNumbersXOR(self, nums: List[int]) -> int:
    frequency_map = Counter(nums)
    duplicate_numbers = [num for num, count in frequency_map.items() if count >= 2]  # Wrong condition!
    return reduce(xor, duplicate_numbers, 0)

Why it's a pitfall: If the array ever contained numbers appearing more than twice (though the problem states only once or twice), this would incorrectly include them in the XOR operation.

Solution to Avoid These Pitfalls:

• Use Counter for efficient O(n) frequency counting
• Filter for exactly count == 2, not any other condition
• Let reduce handle the empty list case naturally with initial value 0
• XOR each qualifying number only once (by iterating through the Counter, not the original array)