Find the XOR of Numbers Which Appear Twice - Solution & Explanation
Problem Statement
You are given an array nums, where each number in the array appears either once or twice.
Return the bitwise XOR of all the numbers that appear twice in the array, or 0 if no number appears twice.
Example 1:
Input: nums = [1,2,1,3]
Output: 1
Explanation:
The only number that appears twice in nums is 1.
Example 2:
Input: nums = [1,2,3]
Output: 0
Explanation:
No number appears twice in nums.
Example 3:
Input: nums = [1,2,2,1]
Output: 3
Explanation:
Numbers 1 and 2 appeared twice. 1 XOR 2 == 3.
Constraints:
1 <= nums.length <= 501 <= nums[i] <= 50- Each number in
numsappears either once or twice.
Approach Overview
Problem Overview: You are given an integer array nums. Some values appear once while others appear exactly twice. The task is to compute the XOR of all numbers that appear exactly two times. If no number appears twice, the result is 0. The key idea is identifying duplicates efficiently and combining them using the XOR operation.
Approach 1: Hashmap-based Frequency Count (Time: O(n), Space: O(n))
Traverse the array and maintain a frequency map using a hash table. For every number in nums, increment its count in the map. After building the frequency table, iterate through the map entries and select values with frequency equal to 2. XOR these values together to produce the final result. Hash table lookups and updates run in constant time on average, so the total runtime is O(n). This method is straightforward and works for any integer range, making it a reliable baseline when solving problems involving counting with a hash table.
Approach 2: Boolean Array for Appearance Tracking (Time: O(n), Space: O(1))
If the value range is small (as in this problem where numbers are bounded), a fixed-size boolean array can replace the hash map. Create a boolean array where the index represents the number and the value indicates whether it has been seen before. Iterate through nums: if the number has not been seen, mark it as seen; if it has already been seen, XOR it into the answer because this is the second occurrence. This avoids maintaining full counts and reduces memory overhead. The algorithm still scans the array once, giving O(n) time complexity while the auxiliary array size remains constant.
The approach relies on properties of bit manipulation. XOR accumulates each duplicated value exactly once when the second appearance is detected. The boolean lookup replaces a hash lookup with a direct index operation.
Recommended for interviews: The boolean array solution is typically preferred because it runs in O(n) time with constant extra space and very simple logic. Interviewers often expect candidates to recognize that the value range allows array indexing instead of a hash map. Starting with the hashmap approach demonstrates understanding of counting problems on an array, then optimizing to constant space shows stronger problem‑solving skill.
Approach 1: Hashmap-based Frequency Count
This approach involves using a hashmap (or dictionary) to count the frequency of each element in the array. After computing the frequencies, iterate over this map to find numbers that appear exactly twice, and calculate their XOR. This approach is straightforward as it leverages hashmap operations to keep track of occurrences efficiently.
We use an integer array hash of size 51 (since the maximum possible value is 50) to store the frequency of each number. Traverse the input array and update the frequency. Afterwards, compute the XOR of numbers that have a frequency of exactly two. Finally, return the result.
Complexity
Time Complexity: O(n), where n is the length of the array since each element is processed a constant number of times.
Space Complexity: O(1), as the hashmap (or array) contains a fixed size of 51.
Approach 2: Boolean Array for Appearance Tracking
This method employs a fixed-size boolean array to monitor whether a number has appeared once or twice. This array can be used to mark numbers as they are encountered and again to verify duplicates, applying an XOR operation once any number is confirmed to appear twice.
Using a boolean array first_appearance to track which numbers have been encountered, the algorithm marks numbers as it processes the input. When a second appearance is detected, an XOR of the respective number is conducted to calculate the final result.
Complexity
Time Complexity: O(n), due to the necessity of processing each element once.
Space Complexity: O(1), native to a boolean array of fixed size.
Approach 3: Counting
We define an array or hash table cnt to record the occurrence of each number.
Next, we traverse the array nums. When a number appears twice, we perform an XOR operation with the answer.
Finally, we return the answer.
The time complexity is O(n), and the space complexity is O(M). Where n is the length of the array nums, and M is the maximum value in the array nums or the number of distinct numbers in the array nums.
Code
Python
Java
C++
Go
TypeScript
Approach 4: Bit Manipulation
Since the given number range in the problem is 1 leq nums[i] leq 50, we can use a 64-bit integer to store the occurrence of each number.
We define an integer mask to record whether each number has appeared.
Next, we traverse the array nums. When a number appears twice, i.e., the x-th bit in the binary representation of mask is 1, we perform an XOR operation with the answer. Otherwise, we set the x-th bit of mask to 1.
Finally, we return the answer.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Hashmap-based Frequency Count | Time Complexity: O(n), where n is the length of the array since each element is processed a constant number of times. |
| Boolean Array for Appearance Tracking | Time Complexity: O(n), due to the necessity of processing each element once. |
| Counting | — |
| Bit Manipulation | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hashmap-based Frequency Count | O(n) | O(n) | General case when the value range is large or unknown |
| Boolean Array for Appearance Tracking | O(n) | O(1) | Best when numbers fall within a small fixed range and direct indexing is possible |
Video Solution
3158. Find the XOR of Numbers Which Appear Twice | EASY | Map | Array | O(n) | LeetCode • Leet's Code • 420 views views
Watch 6 more video solutions →Frequently Asked Questions
Is Find the XOR of Numbers Which Appear Twice easy or hard?
Find the XOR of Numbers Which Appear Twice Python/Java solution
How to solve Find the XOR of Numbers Which Appear Twice in O(n)?
What is the best approach for Find the XOR of Numbers Which Appear Twice?
Is Find the XOR of Numbers Which Appear Twice asked at Google/Amazon/Meta?
What data structure is used in Find the XOR of Numbers Which Appear Twice?
What is the time complexity of Find the XOR of Numbers Which Appear Twice?
Ready to solve this problem?
Practice Find the XOR of Numbers Which Appear Twice with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor