Scale Engineer

Find the XOR of Numbers Which Appear Twice

Easy
#2805Time: 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.
Patterns
Bit Manipulation
Data structures
ArrayHash Table

Prompt

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

3 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

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.

Trade-offs

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

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem