# Find the XOR of Numbers Which Appear Twice
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-the-xor-of-numbers-which-appear-twice)
Canonical: https://scaleengineer.com/dsa/problems/find-the-xor-of-numbers-which-appear-twice
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array, Hash Table
---
## Problem
You are given an array `nums`, where each number in the array appears **either**onceortwice.

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.

# Approaches
## Brute Force with Nested Loops
This approach uses a straightforward, brute-force method to find duplicate numbers. It involves iterating through the array with two nested loops to compare every element with every other element that comes after it. A set is used to keep track of duplicates that have already been accounted for to prevent them from being XORed multiple times.
**Time:** O(n^2), where n is the length of the `nums` array. The nested loops result in a quadratic runtime as each element is compared with every other element. · **Space:** O(k), where k is the number of unique duplicate numbers. In the worst case, k can be up to n/2, making the space complexity O(n).
**Pros:** Simple to understand and implement without complex data structures.
**Cons:** Highly inefficient for larger arrays due to its quadratic time complexity.; Requires extra space to keep track of processed duplicates.
### Explanation
We initialize a result variable `xorResult` to 0 and a `HashSet` called `processedDuplicates`. The outer loop iterates from the first element to the second-to-last element (`i`), and the inner loop iterates from the element after `i` to the last element (`j`). Inside the inner loop, we check if `nums[i]` is equal to `nums[j]`. If they are equal and `nums[i]` has not been processed yet (i.e., not in `processedDuplicates`), we perform a bitwise XOR operation on `xorResult` with `nums[i]` and add `nums[i]` to the `processedDuplicates` set. After the loops complete, `xorResult` holds the bitwise XOR of all numbers that appear twice.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int duplicateNumbersXOR(int[] nums) {
        int xorResult = 0;
        Set<Integer> processedDuplicates = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] == nums[j]) {
                    if (!processedDuplicates.contains(nums[i])) {
                        xorResult ^= nums[i];
                        processedDuplicates.add(nums[i]);
                    }
                }
            }
        }
        return xorResult;
    }
}
```
### Algorithm
*   Initialize a result variable `xorResult` to 0.
*   Initialize a `HashSet` called `processedDuplicates` to store numbers that have already been identified as duplicates.
*   Use a nested loop to compare every element with every other element.
    *   The outer loop runs from `i = 0` to `n-1`.
    *   The inner loop runs from `j = i + 1` to `n-1`.
*   If `nums[i]` equals `nums[j]` and `nums[i]` is not in the `processedDuplicates` set:
    *   It means we've found a new duplicate pair.
    *   XOR `nums[i]` with `xorResult`.
    *   Add `nums[i]` to the `processedDuplicates` set to avoid XORing it again.
*   After the loops complete, return `xorResult`.

## Single Pass with a Set
This approach improves upon the brute-force method by using a `HashSet` to keep track of numbers encountered so far. This allows us to find duplicates in a single pass through the array, leading to a linear time complexity.
**Time:** O(n), where n is the length of the `nums` array. We iterate through the array once, and set operations (add, contains) take O(1) average time. · **Space:** O(k), where k is the number of unique elements in the array. In the worst case, all elements are unique, leading to O(n) space.
**Pros:** Efficient O(n) time complexity.; Conceptually simple and easy to implement.
**Cons:** Requires extra space for the set, which can be O(n) in the worst case (when all elements are unique).
### Explanation
We initialize a result variable `xorResult` to 0 and a `HashSet` called `seen`. We then iterate through each number `num` in the `nums` array. For each `num`, we check if it's already in the `seen` set. A neat trick is to use the boolean return value of `seen.add(num)`. If the number is already present, `add` returns `false`, and we know it's a duplicate. In this case, we XOR the number with our `xorResult`. If the number is not present, `add` returns `true`, and we simply move on. After iterating through all the numbers, `xorResult` will contain the final XOR sum of all duplicate numbers.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int duplicateNumbersXOR(int[] nums) {
        int xorResult = 0;
        Set<Integer> seen = new HashSet<>();
        for (int num : nums) {
            // If the number is already in the set, it's a duplicate.
            if (!seen.add(num)) {
                xorResult ^= num;
            }
        }
        return xorResult;
    }
}
```
### Algorithm
*   Initialize a result variable `xorResult` to 0.
*   Initialize a `HashSet` called `seen` to store numbers encountered so far.
*   Iterate through each number `num` in the `nums` array.
*   For each `num`, attempt to add it to the `seen` set.
*   The `add` method of a `HashSet` returns `false` if the element is already present.
*   If `seen.add(num)` returns `false`, it signifies a duplicate. XOR this `num` with `xorResult`.
*   If it returns `true`, it's the first occurrence of the number, so we do nothing.
*   After the loop, return `xorResult`.

## Constant Space with a Frequency Array
This is the most efficient approach, leveraging the problem's constraints. Since the numbers in the array are small and within a fixed range (`1` to `50`), we can use a simple array as a frequency counter. This avoids the overhead of hashing and provides constant space complexity.
**Time:** O(n + m), where n is the length of `nums` and m is the range of possible values (50). Since m is a constant, the complexity simplifies to O(n). · **Space:** O(1). Since the range of numbers is fixed and small (1 to 50), the size of the `counts` array is constant (51) regardless of the input array's size.
**Pros:** Optimal time complexity of O(n).; Optimal constant space complexity, O(1), due to the fixed-size array.; Very fast in practice due to direct array access instead of hashing.
**Cons:** This approach is only optimal because of the specific constraints on the values in `nums`. It would be less memory-efficient if the numbers could be very large.
### Explanation
This method takes advantage of the constraint that `1 <= nums[i] <= 50`. We first create a frequency array, `counts`, of size 51 (for indices 0 to 50), initialized to all zeros. We iterate through the input array `nums`, and for each number `num`, we increment the count at its corresponding index in the `counts` array. After populating the frequency map, we initialize a result variable `xorResult` to 0. We then iterate through the `counts` array from 1 to 50. If the count for any number `i` is exactly 2, we XOR `i` with `xorResult`. Finally, we return the `xorResult`.

```java
class Solution {
    public int duplicateNumbersXOR(int[] nums) {
        // Constraints: 1 <= nums[i] <= 50
        int[] counts = new int[51];
        for (int num : nums) {
            counts[num]++;
        }

        int xorResult = 0;
        for (int i = 1; i < counts.length; i++) {
            if (counts[i] == 2) {
                xorResult ^= i;
            }
        }
        return xorResult;
    }
}
```
### Algorithm
*   Leverage the constraint that `1 <= nums[i] <= 50`.
*   Create an integer array `counts` of size 51, initialized to zeros, to act as a frequency map.
*   Iterate through the input array `nums`. For each `num`, increment the count at the corresponding index: `counts[num]++`.
*   Initialize a result variable `xorResult` to 0.
*   Iterate through the `counts` array from index 1 to 50.
*   If `counts[i]` is equal to 2, it means the number `i` appeared twice. XOR `i` with `xorResult`.
*   Return `xorResult`.

# Solutions
### Java

```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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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)

```