Set Mismatch

Easy · Bit Manipulation · Explanation and code example

Bitwise XOR

How it works

XOR has the property that a ^ a = 0. If we XOR all numbers in the array with all numbers from 1 to n, pairs cancel out, leaving us with duplicate ^ missing. To separate them, we find a bit where they differ (using the rightmost set bit), then partition all numbers into two groups based on that bit. XORing within each group isolates the duplicate and missing values.

Steps

  1. XOR all array elements with all numbers 1 to n. This gives duplicate ^ missing.
  2. Find the rightmost set bit in the XOR result (this bit differs between duplicate and missing).
  3. Partition all numbers (from array and from 1 to n) into two groups based on this bit.
  4. XOR numbers within each group separately to get two candidates x and y.
  5. Check which candidate appears in the array to identify the duplicate.
  6. Return [duplicate, missing].

Complexity

  • Time complexity: O(n)
  • Space complexity: O(1)

Things to watch for

Confusing the Output Order

The problem asks to return [duplicate, missing] in that specific order. Accidentally swapping the order and returning [missing, duplicate] produces wrong answers even when both numbers are correctly identified.

Not Handling Edge Cases at Array Boundaries

When using the sorting approach, special handling is needed if the missing number is 1 (the first element) or n (the last element). These boundary cases require explicit checks beyond just comparing adjacent elements.

Python code example

from typing import List

class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        N = len(nums)
        # a ^ a = 0
        # xorr = (1 ^ 2 ^ ... N) ^ (nums[0] ^ nums[1] ^ ... nums[N - 1])
        # xorr = missing ^ duplicate
        xorr = 0
        for i in range(1, N + 1):
            xorr ^= i
            xorr ^= nums[i - 1]

        # bit that is set in only one number among (duplicate, missing),
        # will be set in (duplicate ^ missing)
        # take rightMost set bit for simplicity
        rightMostBit = xorr & ~(xorr - 1)

        # divide numbers (from nums, from [1, N]) into two sets w.r.t the rightMostBit
        # xorr the numbers of these sets independently
        x = y = 0
        for i in range(1, N + 1):
            if i & rightMostBit:
                x ^= i
            else:
                y ^= i

            if nums[i - 1] & rightMostBit:
                x ^= nums[i - 1]
            else:
                y ^= nums[i - 1]

        # identify the duplicate number from x and y
        for num in nums:
            if num == x:
                return [x, y]
        return [y, x]

C++ code example

class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        int N = nums.size();
        // a ^ a = 0
        // xorr = (1 ^ 2 ^ ... N) ^ (nums[0] ^ nums[1] ^ ... nums[N - 1])
        // xorr = missing ^ duplicate
        int xorr = 0;
        for (int i = 1; i <= N; i++) {
            xorr ^= i;
            xorr ^= nums[i - 1];
        }

        // bit that is set in only one number among (duplicate, missing),
        // will be set in (duplicate ^ missing)
        // take rightMost set bit for simplicity
        int rightMostBit = xorr & ~(xorr - 1);

        // divide numbers (from nums, from [1, N]) into two sets w.r.t the rightMostBit
        // xorr the numbers of these sets independently
        int x = 0, y = 0;
        for (int i = 1; i <= N; i++) {
            if (i & rightMostBit) {
                x ^= i;
            } else {
                y ^= i;
            }

            if (nums[i - 1] & rightMostBit) {
                x ^= nums[i - 1];
            } else {
                y ^= nums[i - 1];
            }
        }

        // identify the duplicate number from x and y
        for (int num : nums) {
            if (num == x) {
                return {x, y};
            }
        }
        return {y, x};
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations