Set Mismatch

Problem

You have a set of integers s, which originally contains all the numbers from 1 to n. Unfortunately, due to some error, one of the numbers in s got duplicated to another number in the set, which results in repetition of one number and loss of another number.

You are given an integer array nums representing the data status of this set after the error.

Find the number that occurs twice and the number that is missing and return them in the form of an array.

Constraints

• n == nums.length
• 2 <= nums.length <= 104
• 1 <= nums[i] <= 104

Solution

The problem Set Mismatch can be solved using a similar technique as Find the Difference. When an XOR operation is performed on all numbers in the given array and all numbers in range [1, n], then the result becomes r ^ m where r is the repeated number and m the missing number. Since r and m are guaranteed to be different, r ^ m != 0 which means that r ^ m would have at least one bit set. Let n be a number being XOR-ed and lsb be the least significant bit set in r ^ m. Then, we once again XOR all numbers in the given array and all numbers in range [1, n]. However, this time,instead of performing XOR on all numbers, we XOR 2 sets of numbers separately, one which satifies n & lsb == 0 and one that does not. By doing this, we are essentially using a bit from r ^ m as a separator to place all 3 occurrences of rs in one set and the only occurrence of m in the other. When each set is XOR-ed separately, they will each contain r and m, since all other numbers that exists in pairs will cancel out each other.

Implementation

class Solution
{
  public:
    vector<int> findErrorNums(vector<int> &nums)
    {
        int len = nums.size();
        int sum = len * (len + 1) / 2;

        int xor_all = 0;
        for (int i = 0; i < len; i++)
        {
            xor_all ^= nums[i] ^ (i + 1);
            sum -= nums[i];
        }
        int lsb = xor_all & ~(xor_all - 1);

        int xor_arr[2] = {0, 0};
        for (int i = 0; i < len; i++)
        {
            xor_arr[nums[i] & lsb ? 0 : 1] ^= nums[i];
            xor_arr[(i + 1) & lsb ? 0 : 1] ^= i + 1;
        }

        if (xor_arr[1] + sum == xor_arr[0])
            swap(xor_arr[0], xor_arr[1]);

        return vector<int>{xor_arr[0], xor_arr[1]};
    }
};