#3158

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Find the XOR of Numbers Which Appear Twice

Find the XOR of numbers appearing twice by scanning the array and using a hash table for efficient tracking and combination.

array hash table bit manipulation

Problem Statement

You are given an array nums where each number appears either once or twice. Your task is to return the XOR of all numbers that appear exactly twice in the array. If no number appears twice, return 0. The array size and number values are small, allowing a direct scan and hash-based lookup solution.

For example, given nums = [1,2,1,3], the only number appearing twice is 1, so the output is 1. For nums = [1,2,2,1], both 1 and 2 appear twice, so the XOR of 1 and 2 yields 3. Implement an efficient method using array scanning plus hash lookup while respecting the small constraints of the problem.

Examples

Example 1

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

Output: 1

The only number that appears twice in nums is 1.

Example 2

Input: nums = [1,2,3]

Output: 0

No number appears twice in nums .

Example 3

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

Output: 3

Numbers 1 and 2 appeared twice. 1 XOR 2 == 3 .

Constraints

1 <= nums.length <= 50
1 <= nums[i] <= 50
Each number in nums appears either once or twice.

Solution Approach

Hash Set Tracking

Iterate through nums while storing numbers in a hash set. If a number is seen again, XOR it into a result variable. This efficiently captures all duplicates using array scanning plus hash lookup.

Direct XOR Combination

After identifying numbers appearing twice via the hash set, combine them using bitwise XOR. This ensures the final answer represents all repeated numbers without double-counting.

Edge Case Handling

Check for arrays with no duplicates. Since XOR of zero numbers is 0, return 0 when no number appears twice. This handles small arrays and avoids unnecessary computation.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) due to single array scan. Space complexity is O(n) for the hash set storing seen numbers. Small array constraints make this approach efficient.

What Interviewers Usually Probe

Check whether the candidate uses extra space versus in-place tracking for duplicates.
Observe if XOR is applied only to numbers appearing twice, not all numbers.
Notice attention to edge cases where no number repeats or the array length is minimal.

Common Pitfalls or Variants

Common pitfalls

XORing numbers that appear only once, which leads to incorrect results.
Missing edge cases where no number appears twice, forgetting to return 0.
Using nested loops instead of hash lookup, increasing time complexity unnecessarily.

Follow-up variants

Return the XOR of numbers appearing exactly three times instead of twice.
Find the XOR of all numbers appearing an odd number of times in the array.
Implement the solution without using extra space by modifying the array in-place.

FAQ

What is the simplest way to find the XOR of numbers appearing twice?

Use a hash set to track seen numbers while scanning the array, then XOR any number that appears twice.

Does this problem allow numbers to appear more than twice?

No, each number appears either once or twice, so the algorithm focuses only on duplicates.

Can we solve this without extra space?

Yes, by sorting the array and XORing consecutive duplicates, though hash set is more straightforward for small arrays.

How does bit manipulation help in this problem?

XOR allows combining duplicates efficiently, leveraging the property that n XOR n = 0 and n XOR 0 = n.

Why is array scanning plus hash lookup the recommended pattern?

It directly identifies duplicates in one pass while keeping track of seen numbers efficiently, matching the problem constraints.

terminal

Solution

Solution 1: Counting

We define an array or hash table `cnt` to record the occurrence of each number.

1

2

3

4

class Solution:
    def duplicateNumbersXOR(self, nums: List[int]) -> int:
        cnt = Counter(nums)
        return reduce(xor, [x for x, v in cnt.items() if v == 2], 0)

Solution 2: Bit Manipulation

Since the given number range in the problem is $1 \leq \textit{nums}[i] \leq 50$, we can use a $64$-bit integer to store the occurrence of each number.

1

2

3

4

class Solution:
    def duplicateNumbersXOR(self, nums: List[int]) -> int:
        cnt = Counter(nums)
        return reduce(xor, [x for x, v in cnt.items() if v == 2], 0)

Continue Practicing

#2935 maximum strong pair xor ii #2932 maximum strong pair xor i #2897 apply operations on array to maximize sum of squares