LeetCode 3158: Find the XOR of Numbers Which Appear Twice (Frequency Count + XOR Fold)
LeetCode 3158CountingXORToday we solve LeetCode 3158 - Find the XOR of Numbers Which Appear Twice.
Source: https://leetcode.com/problems/find-the-xor-of-numbers-which-appear-twice/
English
Problem Summary
Given an integer array nums, return the XOR of all values that appear exactly twice. If no value appears twice, return 0.
Key Insight
We only care whether each value appears exactly two times. So we can:
- Count frequencies.
- XOR all keys whose frequency is 2.
This is direct and reliable.
Algorithm
1. Create a frequency map (or fixed-size count array if value range is bounded).
2. Traverse nums and count each number.
3. Initialize ans = 0.
4. For every distinct number, if count is 2, do ans ^= number.
5. Return ans.
Complexity Analysis
Let n be length of nums.
Time: O(n).
Space: O(u), where u is number of distinct values.
Common Pitfalls
- Mistakenly XORing numbers appearing at least twice (>=2) instead of exactly twice.
- Forgetting result should be 0 when no number appears twice.
- Assuming sorted input (not required).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int duplicateNumbersXOR(int[] nums) {
java.util.HashMap<Integer, Integer> freq = new java.util.HashMap<>();
for (int x : nums) {
freq.put(x, freq.getOrDefault(x, 0) + 1);
}
int ans = 0;
for (java.util.Map.Entry<Integer, Integer> e : freq.entrySet()) {
if (e.getValue() == 2) {
ans ^= e.getKey();
}
}
return ans;
}
}func duplicateNumbersXOR(nums []int) int {
freq := make(map[int]int)
for _, x := range nums {
freq[x]++
}
ans := 0
for x, c := range freq {
if c == 2 {
ans ^= x
}
}
return ans
}class Solution {
public:
int duplicateNumbersXOR(vector<int>& nums) {
unordered_map<int, int> freq;
for (int x : nums) {
freq[x]++;
}
int ans = 0;
for (auto &[x, c] : freq) {
if (c == 2) {
ans ^= x;
}
}
return ans;
}
};from collections import Counter
from typing import List
class Solution:
def duplicateNumbersXOR(self, nums: List[int]) -> int:
freq = Counter(nums)
ans = 0
for x, c in freq.items():
if c == 2:
ans ^= x
return ansvar duplicateNumbersXOR = function(nums) {
const freq = new Map();
for (const x of nums) {
freq.set(x, (freq.get(x) || 0) + 1);
}
let ans = 0;
for (const [x, c] of freq.entries()) {
if (c === 2) {
ans ^= x;
}
}
return ans;
};中文
题目概述
给定整数数组 nums，把所有出现恰好两次的数字做按位异或，返回结果；若不存在这样的数字，返回 0。
核心思路
题目只关心“出现次数是否等于 2”。因此可以先统计频次，再把频次为 2 的数字依次 XOR 到答案里。
算法步骤
1）用哈希表统计每个数字出现次数。
2）初始化 ans = 0。
3）遍历哈希表，若某数字频次为 2，执行 ans ^= x。
4）返回 ans。
复杂度分析
设数组长度为 n。
时间复杂度：O(n)。
空间复杂度：O(u)，其中 u 是不同数字个数。
常见陷阱
- 把“恰好两次”误写成“至少两次”。
- 忘记没有任何合法数字时应返回 0。
- 以为要先排序，其实不需要。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int duplicateNumbersXOR(int[] nums) {
java.util.HashMap<Integer, Integer> freq = new java.util.HashMap<>();
for (int x : nums) {
freq.put(x, freq.getOrDefault(x, 0) + 1);
}
int ans = 0;
for (java.util.Map.Entry<Integer, Integer> e : freq.entrySet()) {
if (e.getValue() == 2) {
ans ^= e.getKey();
}
}
return ans;
}
}func duplicateNumbersXOR(nums []int) int {
freq := make(map[int]int)
for _, x := range nums {
freq[x]++
}
ans := 0
for x, c := range freq {
if c == 2 {
ans ^= x
}
}
return ans
}class Solution {
public:
int duplicateNumbersXOR(vector<int>& nums) {
unordered_map<int, int> freq;
for (int x : nums) {
freq[x]++;
}
int ans = 0;
for (auto &[x, c] : freq) {
if (c == 2) {
ans ^= x;
}
}
return ans;
}
};from collections import Counter
from typing import List
class Solution:
def duplicateNumbersXOR(self, nums: List[int]) -> int:
freq = Counter(nums)
ans = 0
for x, c in freq.items():
if c == 2:
ans ^= x
return ansvar duplicateNumbersXOR = function(nums) {
const freq = new Map();
for (const x of nums) {
freq.set(x, (freq.get(x) || 0) + 1);
}
let ans = 0;
for (const [x, c] of freq.entries()) {
if (c === 2) {
ans ^= x;
}
}
return ans;
};
Comments