3158. Find the XOR of Numbers Which Appear Twice
Description
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.
Solutions
Solution 1: 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.
Python3
class Solution:
def duplicateNumbersXOR(self, nums: List[int]) -> int:
cnt = Counter(nums)
return reduce(xor, [x for x, v in cnt.items() if v == 2], 0)
Java
class Solution {
public int duplicateNumbersXOR(int[] nums) {
int[] cnt = new int[51];
int ans = 0;
for (int x : nums) {
if (++cnt[x] == 2) {
ans ^= x;
}
}
return ans;
}
}
C++
class Solution {
public:
int duplicateNumbersXOR(vector<int>& nums) {
int cnt[51]{};
int ans = 0;
for (int x : nums) {
if (++cnt[x] == 2) {
ans ^= x;
}
}
return ans;
}
};
Go
func duplicateNumbersXOR(nums []int) (ans int) {
cnt := [51]int{}
for _, x := range nums {
cnt[x]++
if cnt[x] == 2 {
ans ^= x
}
}
return
}
TypeScript
function duplicateNumbersXOR(nums: number[]): number {
const cnt: number[] = Array(51).fill(0);
let ans: number = 0;
for (const x of nums) {
if (++cnt[x] === 2) {
ans ^= x;
}
}
return ans;
}
Solution 2: Bit Manipulation
Since the given number range in the problem is $1 \leq \textit{nums}[i] \leq 50$, we can use a $64$-bit integer to store the occurrence of each number.
We define an integer $\textit{mask}$ to record whether each number has appeared.
Next, we traverse the array $\textit{nums}$. When a number appears twice, i.e., the $x$-th bit in the binary representation of $\textit{mask}$ is $1$, we perform an XOR operation with the answer. Otherwise, we set the $x$-th bit of $\textit{mask}$ to $1$.
Finally, we return the answer.
The time complexity is $O(n)$, where $n$ is the length of the array $\textit{nums}$. The space complexity is $O(1)$.
Python3
class Solution:
def duplicateNumbersXOR(self, nums: List[int]) -> int:
ans = mask = 0
for x in nums:
if mask >> x & 1:
ans ^= x
else:
mask |= 1 << x
return ans
Java
class Solution {
public int duplicateNumbersXOR(int[] nums) {
int ans = 0;
long mask = 0;
for (int x : nums) {
if ((mask >> x & 1) == 1) {
ans ^= x;
} else {
mask |= 1L << x;
}
}
return ans;
}
}
C++
class Solution {
public:
int duplicateNumbersXOR(vector<int>& nums) {
int ans = 0;
long long mask = 0;
for (int x : nums) {
if (mask >> x & 1) {
ans ^= x;
} else {
mask |= 1LL << x;
}
}
return ans;
}
};
Go
func duplicateNumbersXOR(nums []int) (ans int) {
mask := 0
for _, x := range nums {
if mask>>x&1 == 1 {
ans ^= x
} else {
mask |= 1 << x
}
}
return
}
TypeScript
function duplicateNumbersXOR(nums: number[]): number {
let ans = 0;
let mask = 0n;
for (const x of nums) {
if ((mask >> BigInt(x)) & 1n) {
ans ^= x;
} else {
mask |= 1n << BigInt(x);
}
}
return ans;
}