We can use XOR bitwise operation. XORing a number by itself results in 0 (A ^ A = 0), and XORing a number with 0 results in the number itself (A ^ 0 = A). Since every element appears twice except for one, XORing all elements together will cancel out the duplicates and leave only the single number.
// Pseudocode: Use a hash map to count frequencies.
// 1. Initialize a hash map `counts`.
// 2. Iterate through nums and populate counts.
// 3. Iterate through counts and return the key with value 1.
class Solution {
public:
int singleNumber(vector<int>& nums) {
unordered_map<int, int> counts;
for (int n : nums) {
counts[n]++;
}
for (auto const& [n, c] : counts) {
if (c == 1) {
return n;
}
}
return -1;
}
};// Pseudocode:
// 1. Initialize res = 0.
// 2. Iterate through each n in nums.
// 3. res = res ^ n (XOR operation).
// 4. Return res.
class Solution {
public:
int singleNumber(vector<int>& nums) {
int res = 0;
for (int n : nums) {
res ^= n;
}
return res;
}
};Time: O(n) to iterate through the array. Space: O(1) for the optimal XOR approach.
- Array of size 1. Loop runs once, returns the element.
- Negative numbers. XOR works seamlessly with 2’s complement negative integers built into C++.
Whenever you see ‘every element appears twice except for one’, think XOR. It’s the ultimate trick to finding the odd one out without extra space.