Find the XOR of Numbers Which Appear Twice

Difficulty: Easy | Acceptance: 78.90% | Paid: No Topics: Array, Hash Table, Bit Manipulation

You are given a positive integer array nums.

Return the XOR of all the numbers that appear twice in the array. If no number appears twice, return 0.

• Examples
• Constraints
• Hash Map Frequency Count
• Sorting
• Fixed Array Counting

Examples

Input: nums = [1,2,1,3]
Output: 1
Explanation: The number 1 appears twice, the XOR of 1 is 1.

Input: nums = [1,2,3]
Output: 0
Explanation: No number appears twice, so the result is 0.

Input: nums = [1,2,2,1]
Output: 3
Explanation: The numbers 1 and 2 appear twice. 1 XOR 2 = 3.

Constraints

1 <= nums.length <= 50
1 <= nums[i] <= 50

Hash Map Frequency Count

Intuition We can iterate through the array and count the frequency of each number using a hash map. Then, we iterate through the map entries and XOR the keys where the value is exactly 2.

Steps

• Initialize an empty hash map and a result variable set to 0.
• Iterate through the input array, incrementing the count for each number in the hash map.
• Iterate through the hash map entries. If a number’s count is 2, XOR it with the result.
• Return the result.

class Solution:
    def duplicateNumbersXOR(self, nums: List[int]) -> int:
        counts = {}
        res = 0
        for n in nums:
            counts[n] = counts.get(n, 0) + 1
        for k, v in counts.items():
            if v == 2:
                res ^= k
        return res

Complexity

• Time: O(n)
• Space: O(n)
• Notes: Uses extra space proportional to the number of unique elements.

Sorting

Intuition If we sort the array, duplicate numbers will be adjacent to each other. We can then iterate through the sorted array and check if nums[i] equals nums[i+1].

Steps

• Sort the input array in ascending order.
• Initialize a result variable to 0 and an index i to 0.
• Iterate while i < nums.length - 1.
• If nums[i] == nums[i+1], XOR nums[i] with the result and increment i by 2 to skip the duplicate pair.
• Otherwise, increment i by 1.
• Return the result.

class Solution:
    def duplicateNumbersXOR(self, nums: List[int]) -> int:
        nums.sort()
        res = 0
        i = 0
        n = len(nums)
        while i < n - 1:
            if nums[i] == nums[i+1]:
                res ^= nums[i]
                i += 2
            else:
                i += 1
        return res

Complexity

• Time: O(n log n)
• Space: O(1) or O(n) depending on the sorting algorithm’s space complexity.
• Notes: Modifies the input array.

Fixed Array Counting

Intuition The problem constraints state that 1 <= nums[i] <= 50. Since the range of possible values is very small and fixed, we can use an array of size 51 to count frequencies instead of a hash map. This is often faster and more memory-efficient for small ranges.

Steps

• Initialize an integer array count of size 51 with all zeros.
• Iterate through nums, incrementing count[num] for each element.
• Initialize a result variable to 0.
• Iterate from 1 to 50. If count[i] == 2, XOR i with the result.
• Return the result.

class Solution:
    def duplicateNumbersXOR(self, nums: List[int]) -> int:
        count = [0] * 51
        for n in nums:
            count[n] += 1
        res = 0
        for i in range(1, 51):
            if count[i] == 2:
                res ^= i
        return res

Complexity

• Time: O(n)
• Space: O(1) (The array size is fixed at 51 regardless of input size).
• Notes: Optimal approach given the specific constraints.