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 <= 50
1 <= nums[i] <= 50
- Each number in
nums
appears 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
.
1 2 3 4 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 10 |
|
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)$.
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|