Find the XOR of Numbers Which Appear Twice

Easy
998.

Find the XOR of Numbers Which Appear Twice

Find the XOR of Numbers Which Appear Twice is an easy coding problem on arrays, hash table and bit manipulation, asked in Amazon, Google and Mindtree interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var duplicateNumbersXOR = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find the XOR of Numbers Which Appear Twice — Solution

Find the XOR of Numbers Which Appear Twice solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Find the XOR of Numbers Which Appear Twice is an easy coding problem on arrays, hash table and bit manipulation, asked in Amazon, Google and Mindtree interviews.

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.

Hints for Find the XOR of Numbers Which Appear Twice

  1. Hint 1

    Count how often each value appears.

  2. Hint 2

    XOR together the values whose count is exactly 2.

  3. Hint 3

    The empty XOR is 0, which is already the required fallback.

How to solve Find the XOR of Numbers Which Appear Twice

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

Approach

  1. Tally each value.
  2. 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

Java

public static int duplicateNumbersXOR(int[] nums) {
    Map<Integer, Integer> count = new HashMap<>();
    for (int v : nums) count.merge(v, 1, Integer::sum);
    int out = 0;
    for (Map.Entry<Integer, Integer> e : count.entrySet()) {
        if (e.getValue() == 2) out ^= e.getKey();
    }
    return out;
}

C++

int duplicateNumbersXOR(vector<int>& nums) {
    unordered_map<int, int> count;
    for (int v : nums) count[v]++;
    int out = 0;
    for (auto& e : count) {
        if (e.second == 2) out ^= e.first;
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets