Find the XOR of Numbers Which Appear Twice — Solution
Find the XOR of Numbers Which Appear Twice solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Find the XOR of Numbers Which Appear Twice is an easy coding problem on arrays, hash table and bit manipulation, asked in Amazon, Google and Mindtree interviews.
- Difficulty: Easy
- Topics: Arrays, Hash Table, Bit Manipulation
- Asked at: Amazon, Google, Mindtree
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Each number in nums appears either once or twice.
Return the bitwise XOR of all the numbers that appear twice, or 0 if none does.
Example 1
Input: nums = [1,2,1,3]
Output: 1
Explanation: Only 1 appears twice.
Example 2
Input: nums = [1,2,3]
Output: 0
Explanation: Nothing repeats.
Example 3
Input: nums = [1,2,2,1]
Output: 3
Explanation: `1 XOR 2 = 3`.
Constraints
1 <= nums.length <= 501 <= nums[i] <= 50Each number in nums appears either once or twice.
Hints for Find the XOR of Numbers Which Appear Twice
Hint 1
Count how often each value appears.
Hint 2
XOR together the values whose count is exactly 2.
Hint 3
The empty XOR is 0, which is already the required fallback.
How to solve Find the XOR of Numbers Which Appear Twice
Count the occurrences, then XOR the values that occur twice.
Approach
- Tally each value.
- XOR every value whose tally is 2 into a running result, starting from 0.
Why it works
Starting the accumulator at 0 gives the "no duplicates" case for free, since XOR's identity is 0. A one-pass variant also works: keep a seen set and XOR a value in the moment it is met for the second time — the values appear at most twice, so no third sighting can undo it.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- XOR-ing every element cancels the duplicates instead of collecting them.
- Values appearing once must be excluded.
- The answer for no duplicates is 0, not -1.
Reference solution
Python
from typing import List
from collections import Counter
def duplicateNumbersXOR(nums: List[int]) -> int:
out = 0
for v, c in Counter(nums).items():
if c == 2:
out ^= v
return outJava
public static int duplicateNumbersXOR(int[] nums) {
Map<Integer, Integer> count = new HashMap<>();
for (int v : nums) count.merge(v, 1, Integer::sum);
int out = 0;
for (Map.Entry<Integer, Integer> e : count.entrySet()) {
if (e.getValue() == 2) out ^= e.getKey();
}
return out;
}C++
int duplicateNumbersXOR(vector<int>& nums) {
unordered_map<int, int> count;
for (int v : nums) count[v]++;
int out = 0;
for (auto& e : count) {
if (e.second == 2) out ^= e.first;
}
return out;
}JavaScript
var duplicateNumbersXOR = function(nums) {
var count = new Map(), i;
for (i = 0; i < nums.length; i++) {
var cur = count.get(nums[i]);
count.set(nums[i], (cur === undefined ? 0 : cur) + 1);
}
var out = 0;
count.forEach(function(c, v) {
if (c === 2) out ^= v;
});
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets