Watch 8 video solutions for Find the XOR of Numbers Which Appear Twice, a easy level problem involving Array, Hash Table, Bit Manipulation. This walkthrough by Leet's Code has 350 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 50nums appears either once or twice.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 | 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 |