Find the XOR of Numbers Which Appear Twice — Easy Problem & Solution

Each number in nums appears either once or twice. Return the bitwise XOR of all the numbers that appear twice, or 0 if none does.

Difficulty: Easy
Topics: Arrays, Hash Table, Bit Manipulation
Asked at: Amazon, Google, Mindtree
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Each number in nums appears either once or twice.

Return the bitwise XOR of all the numbers that appear twice, or 0 if none does.

Example 1

Input: nums = [1,2,1,3]
Output: 1
Explanation: Only 1 appears twice.

Example 2

Input: nums = [1,2,3]
Output: 0
Explanation: Nothing repeats.

Example 3

Input: nums = [1,2,2,1]
Output: 3
Explanation: `1 XOR 2 = 3`.

Constraints

1 <= nums.length <= 50
1 <= nums[i] <= 50
Each number in nums appears either once or twice.

How to solve Find the XOR of Numbers Which Appear Twice

Count the occurrences, then XOR the values that occur twice.

Approach

Tally each value.
XOR every value whose tally is 2 into a running result, starting from 0.

Why it works

Starting the accumulator at 0 gives the "no duplicates" case for free, since XOR's identity is 0. A one-pass variant also works: keep a seen set and XOR a value in the moment it is met for the second time — the values appear at most twice, so no third sighting can undo it.

Complexity

Time — O(n)
Space — O(n)

Pitfalls

XOR-ing every element cancels the duplicates instead of collecting them.
Values appearing once must be excluded.
The answer for no duplicates is 0, not -1.

Reference solution

Python

from typing import List
from collections import Counter

def duplicateNumbersXOR(nums: List[int]) -> int:
    out = 0
    for v, c in Counter(nums).items():
        if c == 2:
            out ^= v
    return out

JavaScript

var duplicateNumbersXOR = function(nums) {
    var count = new Map(), i;
    for (i = 0; i < nums.length; i++) {
        var cur = count.get(nums[i]);
        count.set(nums[i], (cur === undefined ? 0 : cur) + 1);
    }
    var out = 0;
    count.forEach(function(c, v) {
        if (c === 2) out ^= v;
    });
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue