LeetCode 3158 - Find the XOR of Numbers Which Appear Twice

LeetCode Problem 3158

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Bit Manipulation

Solution

Problem Understanding

This problem asks us to find all numbers in the array that appear exactly twice and compute the bitwise XOR of those numbers.

The input is an integer array nums. The problem guarantees that every value appears either once or twice, never more than twice. Our task is not to count how many duplicate occurrences exist, but rather to identify which distinct values occur twice and XOR those values together.

For example, if the array is [1,2,2,1], then both 1 and 2 appear twice. We therefore compute:

1 XOR 2 = 3

and return 3.

If no number appears twice, such as in [1,2,3], then there are no values to include in the XOR operation, so the answer is 0.

The constraints are very small. The array length is at most 50, and each value is between 1 and 50. This means even relatively inefficient solutions would be acceptable. However, we can still design a clean and efficient solution using a hash set.

Several edge cases are worth noting:

• An array containing only one element can never contain a duplicate, so the answer must be 0.
• An array where every value appears once should return 0.
• An array where multiple values appear twice should XOR all of them together.
• Since the problem guarantees each number appears at most twice, we never need to handle frequencies greater than two.

Approaches

Brute Force

A straightforward approach is to examine every number and count how many times it appears in the array.

For each element, we can scan the entire array and compute its frequency. If the frequency is 2, we include that value in the final XOR result.

This approach is correct because every value's frequency is computed exactly. However, each frequency calculation requires scanning the whole array, resulting in quadratic time complexity.

Although the constraints are small enough that this would pass, it is not the most efficient solution.

Optimal Approach: Hash Set

The key observation is that we only need to know whether we have seen a number before.

Since every value appears either once or twice, the second time we encounter a number we immediately know it is a duplicate value that should be included in the answer.

We maintain a set containing all numbers seen so far:

• If the current number has not been seen, add it to the set.
• If it has already been seen, this is its second occurrence, so XOR it into the answer.

Because each duplicate value is encountered exactly once as a "second occurrence", each duplicated number contributes exactly one time to the final XOR.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Count frequency of every element by scanning the array repeatedly
Optimal	O(n)	O(n)	Use a hash set to detect second occurrences immediately

Algorithm Walkthrough

1. Create an empty hash set called seen to store numbers that have already appeared.
2. Initialize a variable result to 0. This variable will maintain the XOR of all numbers that appear twice.
3. Iterate through each number in nums.
4. For the current number, check whether it already exists in seen.
5. If the number is not present, add it to seen. This means it is the first time we have encountered that value.
6. If the number is already present, this must be its second occurrence because the problem guarantees values appear at most twice. XOR the number into result.
7. Continue until all elements have been processed.
8. Return result.

Why it works

The set always contains exactly the values that have appeared once so far. When a value is encountered again, we know it is appearing for the second time. Because each duplicated value reaches this condition exactly once, every number that appears twice is XORed into result exactly one time. Values appearing once are never XORed into the answer. Therefore, the final value of result is precisely the XOR of all numbers that appear twice.

Python Solution

from typing import List

class Solution:
    def duplicateNumbersXOR(self, nums: List[int]) -> int:
        seen = set()
        result = 0

        for num in nums:
            if num in seen:
                result ^= num
            else:
                seen.add(num)

        return result

The implementation directly follows the algorithm described above.

The seen set records every value encountered for the first time. As we iterate through the array, we check whether the current number is already present in the set.

If it is not present, we add it to the set. If it is already present, we know this is the second occurrence of that value, so we update the running XOR using result ^= num.

Because the problem guarantees each value appears at most twice, every duplicated number contributes exactly once to the XOR result. After processing the entire array, result contains the required answer and is returned.

Go Solution

func duplicateNumbersXOR(nums []int) int {
    seen := make(map[int]bool)
    result := 0

    for _, num := range nums {
        if seen[num] {
            result ^= num
        } else {
            seen[num] = true
        }
    }

    return result
}

The Go implementation uses a map[int]bool in place of Python's set. The logic remains identical. When a value is encountered for the first time, it is recorded in the map. When encountered again, it is XORed into the result.

There are no integer overflow concerns because all values are between 1 and 50. An empty slice would also be handled correctly, although the problem guarantees at least one element.

Worked Examples

Example 1

Input: nums = [1,2,1,3]

Step	Current Number	Seen Set	Result
Start	-	{}	0
1	1	{1}	0
2	2	{1,2}	0
3	1	{1,2}	1
4	3	{1,2,3}	1

Final answer: 1

Example 2

Input: nums = [1,2,3]

Step	Current Number	Seen Set	Result
Start	-	{}	0
1	1	{1}	0
2	2	{1,2}	0
3	3	{1,2,3}	0

Final answer: 0

Example 3

Input: nums = [1,2,2,1]

Step	Current Number	Seen Set	Result
Start	-	{}	0
1	1	{1}	0
2	2	{1,2}	0
3	2	{1,2}	2
4	1	{1,2}	3

Final answer: 3

Because:

2 XOR 1 = 3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is processed exactly once
Space	O(n)	The hash set may store every distinct value

The algorithm performs a single pass through the array. Every set lookup and insertion is expected O(1), so the total running time is O(n). The auxiliary space is O(n) because, in the worst case, all values are distinct and must be stored in the set.

Test Cases

sol = Solution()

assert sol.duplicateNumbersXOR([1, 2, 1, 3]) == 1  # one duplicated value
assert sol.duplicateNumbersXOR([1, 2, 3]) == 0  # no duplicates
assert sol.duplicateNumbersXOR([1, 2, 2, 1]) == 3  # two duplicated values

assert sol.duplicateNumbersXOR([5]) == 0  # minimum size array
assert sol.duplicateNumbersXOR([7, 7]) == 7  # single duplicated value
assert sol.duplicateNumbersXOR([1, 1, 2, 2, 3, 3]) == 0  # XOR cancels to zero
assert sol.duplicateNumbersXOR([50, 50]) == 50  # maximum value boundary
assert sol.duplicateNumbersXOR([1, 2, 3, 4, 5]) == 0  # all unique
assert sol.duplicateNumbersXOR([10, 20, 10, 30, 20]) == 30  # multiple duplicates
assert sol.duplicateNumbersXOR([8, 8, 9, 10, 10]) == 2  # 8 XOR 10 = 2

Test Summary

Test	Why
[1,2,1,3]	Single duplicated value
[1,2,3]	No duplicates present
[1,2,2,1]	Multiple duplicated values
[5]	Minimum array size
[7,7]	Smallest duplicate case
[1,1,2,2,3,3]	XOR result becomes zero
[50,50]	Maximum allowed value
[1,2,3,4,5]	All elements unique
[10,20,10,30,20]	Multiple duplicates mixed with unique values
[8,8,9,10,10]	Verifies XOR accumulation across duplicates

Edge Cases

One important edge case is an array with no duplicated values, such as [1,2,3]. A buggy implementation might accidentally XOR every value or fail to distinguish between unique and duplicated elements. In our solution, a number is only XORed when it is encountered for the second time, so the result correctly remains 0.

Another important case is an array containing exactly one duplicated value, such as [7,7]. Some implementations that compute frequencies incorrectly may count the duplicate twice. Our approach XORs the value only when the second occurrence is seen, so the answer is correctly 7.

A third edge case occurs when several duplicated values produce an XOR result of zero, such as [1,1,2,2,3,3]. Since 1 XOR 2 XOR 3 = 0, the correct answer is zero even though duplicates exist. Our implementation naturally handles this because it follows the XOR operation exactly rather than counting duplicates.

A final edge case is the smallest possible input size, such as [5]. Since no value can appear twice in a single-element array, the answer must be 0. The algorithm processes the lone element, adds it to the set, never performs a XOR operation, and returns 0.