Set Mismatch

• LeetCode: Set Mismatch

• Problem:

The set S originally contains numbers from 1 to n. But unfortunately, due to the data error, one of the numbers in the set got duplicated to another number in the set, which results in repetition of one number and loss of another number.

Given an array nums representing the data status of this set after the error. Your task is to firstly find the number occurs twice and then find the number that is missing. Return them in the form of an array.

• Note:

1. The given array size will in the range [2, 10000].

2. The given array's numbers won't have any order.

• Examples:

Input: nums = [1,2,2,4]
Output: [2,3]

• Analysis:

Solution1. 
    Sort array and use "xor" to find the miss number and the duplicate number.

    For the duplicated number, arr[i] == arr[i + 1]

    For the miss number, num = 1 ^ 2 ^ ... ^ n ^ arr[0] ^ arr[1] ^ ... ^ arr[len - 1] except for the duplicate number, len is the length of array

Solution2.
    Use a hashmap to store <nums[i], count>, and use "xor" to find the miss number.

    The count in hashmap > 2 is the duplicate number.

    For the miss number, num = 1 ^ 2 ^ ... ^ n ^ arr[0] ^ arr[1] ^ ... ^ arr[len - 1] except for the duplicate number, len is the length of array.

• Solution - Sort:

• Code - Java:

class Solution {
    public int[] findErrorNums(int[] nums) {
        int[] result = new int[2];
        int len = nums.length;
        Arrays.sort(nums);
        int num = 0;
        for (int i = 0; i < len - 1; i++) {
            num ^= (i + 1);
            if (nums[i] == nums[i + 1]) {
                result[0] = nums[i];
            } else {
                num ^= nums[i];
            }
        }
        result[1] = num ^ len ^ nums[len - 1];
        return result;
    }
}

• Code - C++:

class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        vector<int> result(2, 0);
        int len = nums.size();
        sort(nums.begin(), nums.end());
        int num = 0;
        for (int i = 0; i < len - 1; i++) {
            num ^= (i + 1);
            if (nums[i] == nums[i + 1]) {
                result[0] = nums[i];
            } else {
                num ^= nums[i];
            }
        }
        result[1] = num ^ len ^ nums[len - 1];
        return result;
    }
};

• Code - Python:

class Solution(object):
    def findErrorNums(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """

        result = [0, 0]
        numsLen = len(nums)
        nums = sorted(nums)
        num = 0
        for i in range(numsLen - 1):
            num ^= (i + 1)
            if nums[i] == nums[i + 1]:
                result[0] = nums[i]
            else:
                num ^= nums[i]
        result[1] = num ^ numsLen ^ nums[numsLen - 1]
        return result

• Time Complexity: O(NLOGN), N is the length of input array.
• Space Complexity: O(1)

• Solution - HashMap

• Code - Java:

class Solution {
    public int[] findErrorNums(int[] nums) {
        int[] result = new int[2];
        int len = nums.length;
        Map<Integer, Integer> counts = new HashMap<Integer, Integer>();
        int num = 0;
        for (int i = 0; i < len; i++) {
            num ^= (i + 1);
            if (counts.containsKey(nums[i])) {
                result[0] = nums[i];
            } else {
                counts.put(nums[i], 1);
                num ^= nums[i];
            }
        }
        result[1] = num;
        return result;
    }
}

• Code - C++:

class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        vector<int> result(2, 0);
        map<int, int> counts;
        int len = nums.size();
        int num = 0;
        for (int i = 0; i < len; i++) {
            num ^= (i + 1);
            if (counts.find(nums[i]) != counts.end()) {
                result[0] = nums[i]; 
            } else {
                counts.insert(pair<int, int>(nums[i], 1));
                num ^= nums[i];
            }
        }
        result[1] = num;
        return result;
    }
}

• Code - Python:

class Solution(object):
    def findErrorNums(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        result = [0, 0]
        numsLen = len(nums)
        counts = {}
        num = 0
        for i in range(numsLen):
            num ^= (i + 1)
            if nums[i] in counts:
                result[0] = nums[i]
            else:
                counts[nums[i]] = 1
                num ^= nums[i]
        result[1] = num
        return result

• Time Complexity: O(N), N is the length of input array
• Space Complexity: O(N), N is the length of input array