Find the XOR of Numbers Which Appear Twice

EASY

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.

Approaches

Checkout 3 different approaches to solve Find the XOR of Numbers Which Appear Twice. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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.

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

Complexity Analysis

Time Complexity: 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 Complexity: 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 and Cons

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).

Code Solutions

Checking out 3 solutions in different languages for Find the XOR of Numbers Which Appear Twice. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Find the XOR of Numbers Which Appear Twice

Patterns:

Bit Manipulation

Data Structures:

ArrayHash Table

Find the XOR of Numbers Which Appear Twice

Description

Approaches

Single Pass with a Set

Algorithm

Complexity Analysis

Pros and Cons

Code Solutions

Video Solution

Similar Questions

Patterns:

Data Structures:

On this page

Subscribe to Scale Engineer newsletter