3158. Find the XOR of Numbers Which Appear Twice

EasyBit ManipulationArrayHash Table

Problem Description

You are given an array nums, where each number in the array appears either once or twice. Your task is to return the bitwise XOR of all the numbers that appear twice in the array, or return 0 if no number appears twice.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

To solve this problem, we need to identify numbers in the array that appear exactly twice and compute their bitwise XOR. The XOR operation has an interesting property: for any integer a, a XOR a equals 0 and a XOR 0 equals a. This property will help us consolidate multiple integers effectively.

Count Occurrences: First, we count the occurrences of each number using a hash table or dictionary. This helps us easily determine which numbers appear twice.
XOR Twice-Appearing Numbers: We iterate through the dictionary and perform the XOR operation on those numbers that appear exactly twice. The reduce function in Python can be used here to accumulate the XOR result.
Return Result: If no numbers appear twice, the result will be 0, as performing an XOR with an empty set or not finding any valid numbers defaults the result to 0. Else, we get the XOR of those repeating numbers.

This approach effectively separates the numbers that meet the condition from those that do not and uses XOR to compute the desired result efficiently.

Solution Approach

The solution is implemented using the following steps, employing concepts of counting and leveraging the properties of the XOR operation:

Counting Occurrences:
- Utilize a hash table or dictionary to store the occurrences of each number in the array nums. This is efficiently handled by using collections.Counter in Python which will automatically count each number's occurrences.
```
cnt = Counter(nums)
```

Filter and XOR Calculation:

Traverse the dictionary of counted numbers. For each number that occurs exactly twice, apply the XOR operation to cumulatively form the result.
The list comprehension [x for x, v in cnt.items() if v == 2] extracts all numbers with a count of exactly two.

[x for x, v in cnt.items() if v == 2]

Use the reduce function along with the xor operator from Python's operator module to compute the final XOR of these numbers.

from functools import reduce
from operator import xor
result = reduce(xor, [x for x, v in cnt.items() if v == 2], 0)

Return the Output:
- The final value of the result is returned. If no number appears twice, the XOR of an empty list with 0 is 0, which correctly handles the edge case.

The complete implementation is efficient as it navigates the list of numbers and then processes the hash table to perform the XOR operation.

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)

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's go through an example to better understand the solution approach.

Example:

Consider an array nums: [1, 2, 3, 2, 4, 5, 5].

Step 1: Counting Occurrences

First, we use a counter to count how many times each number appears in the array. The result here would be:

1: 1
2: 2
3: 1
4: 1
5: 2

Step 2: Filter and XOR Calculation

Next, we need to identify numbers that appear exactly twice. From our counted occurrences, 2 and 5 appear twice. We will XOR these numbers.

Twice Appearing Numbers: [2, 5]

We then apply the XOR operation on these numbers:

Compute 2 XOR 5. In binary, this is:

2 = 010
5 = 101
----------
    = 111 (which is 7 in decimal)

Step 3: Return the Output

The final value after performing XOR on [2, 5] is 7. Hence, the XOR of all numbers appearing twice is 7.

The solution leverages the properties of XOR and counts efficiently to consolidate the result for this problem.

Solution Implementation

1from typing import List
2from collections import Counter
3from functools import reduce
4from operator import xor
5
6class Solution:
7    def duplicateNumbersXOR(self, nums: List[int]) -> int:
8        # Create a counter object to count the frequency of each number in the list
9        num_count = Counter(nums)
10      
11        # Use the reduce function along with xor to find the result of XOR-ing all
12        # numbers that have exactly two occurrences
13        # Initialize reduce function with 0 as the starting value
14        return reduce(xor, [num for num, count in num_count.items() if count == 2], 0)
15

1class Solution {
2    public int duplicateNumbersXOR(int[] nums) {
3        // Array to count occurrences of numbers from 0 to 50
4        int[] count = new int[51];
5        int result = 0;
6
7        // Iterate over each number in the input array
8        for (int num : nums) {
9            // Increment the count for the current number
10            if (++count[num] == 2) {
11                // If the number appears twice, XOR it with the result
12                result ^= num;
13            }
14        }
15
16        // Return the result after processing all numbers
17        return result;
18    }
19}
20

1#include <vector>
2
3class Solution {
4public:
5    int duplicateNumbersXOR(std::vector<int>& nums) {
6        int count[51] = {}; // Initialize an array to count occurrences of numbers 0 through 50
7        int answer = 0; // Variable to store the XOR of numbers that appear exactly twice
8
9        // Iterate over each number in the given vector
10        for (int num : nums) {
11            if (++count[num] == 2) { // Increment the count for the current number and check if it reaches 2
12                answer ^= num; // Perform XOR with the number if it appears exactly twice
13            }
14        }
15      
16        return answer; // Return the result which contains XOR of all numbers appearing twice
17    }
18};
19

1/**
2 * This function finds the number that appears exactly twice in the input array using XOR.
3 * It assumes the numbers in the array are between 0 and 50 inclusive.
4 * 
5 * @param nums - Array of numbers in which we search for a duplicate.
6 * @returns The number that appears exactly twice.
7 */
8function duplicateNumbersXOR(nums: number[]): number {
9    // Create an array to count occurrences of each number from 0 to 50
10    const count: number[] = Array(51).fill(0);
11    let result: number = 0;
12
13    // Iterate through each number in the input array
14    for (const num of nums) {
15        // Increment the count for the current number
16        if (++count[num] === 2) {
17            // Use XOR to toggle the result with the current number if it appears twice
18            result ^= num;
19        }
20    }
21    // Return the number that appears exactly twice
22    return result;
23}
24

Time and Space Complexity

The time complexity of the code is O(n) because it iterates over the list nums to count the occurrences of each element, and then filters the counted elements to find those with exactly two occurrences. Another iteration is done over these filtered elements to apply the XOR operation.

The space complexity of the code is O(M), where M is the number of distinct elements in the list nums. This space is used to store the counts of each number in a Counter object.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Pre-order traversal

Post-order traversal

In-order traversal

Level-order traversal

I don't know