Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/645.html

645. Set Mismatch (Easy)

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.

Example 1:

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

Note:

  1. The given array size will in the range [2, 10000].
  2. The given array’s numbers won’t have any order.

Solution 1. unordered_map

// OJ: https://leetcode.com/problems/set-mismatch
// Time: O(N)
// Space: O(N)
class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        unordered_map<int, int> m;
        for (auto n : nums) m[n]++;
        int missing, dup;
        for (int i = 1; i <= nums.size(); ++i) {
            if (!m[i]) missing = i;
            if (m[i] == 2) dup = i;
        }
        return { dup, missing };
    }
};

Solution 2. Sort

// OJ: https://leetcode.com/problems/set-mismatch/
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int dup, missing = 1;
        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i] == nums[i - 1]) dup = nums[i];
            else if (nums[i] > nums[i - 1] + 1) missing = nums[i - 1] + 1;
        }
        return { dup, nums.back() != nums.size() ? nums.size() : missing };
    }
};

Solution 3. Extra Counts Array

Same idea as Solution 1, but Solution 1 actually requires 2N space, while this approach requires N space.

// OJ: https://leetcode.com/problems/set-mismatch/solution/
// Time: O(N)
// Space: O(N)
class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        vector<int> cnts(nums.size(), 0);
        int dup, missing;
        for (int n : nums) cnts[n - 1]++;
        for (int i = 0; i < cnts.size(); ++i) {
            if (cnts[i] == 0) missing = i + 1;
            else if (cnts[i] == 2) dup = i + 1;
        }
        return { dup, missing };
    }
};

Solution 4. Using Constant Space

If we can encode the Counts Array into nums, we can save space.

When we visit a number n in nums, we invert nums[abs(n) - 1]. If the number n just appears once, the corresponding nums[abs(n) - 1] will be negative. When we see a negative nums[abs(n) - 1], it means n has been visited – it’s the duplicate.

If nums[i] is left positive, then i + 1 is the missing number.

// OJ: https://leetcode.com/problems/set-mismatch/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        int dup, missing;
        for (int n : nums) {
            if (nums[abs(n) - 1] < 0) dup = abs(n);
            else nums[abs(n) - 1] *= -1;
        }
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] > 0) missing = i + 1;
        }
        return { dup, missing };
    }
};
  • class Solution {
        public int[] findErrorNums(int[] nums) {
            Arrays.sort(nums);
            int length = nums.length;
            int sum = length * (length + 1) / 2;
            int actualSum = 0;
            for (int num : nums)
                actualSum += num;
            int mismatch = 0;
            for (int i = 1; i < length; i++) {
                if (nums[i] == nums[i - 1]) {
                    mismatch = nums[i];
                    break;
                }
            }
            int difference = sum - actualSum;
            int missing = mismatch + difference;
            int[] ret = {mismatch, missing};
            return ret;
        }
    }
    
    ############
    
    class Solution {
        public int[] findErrorNums(int[] nums) {
            int eor = 0;
            for (int i = 1; i <= nums.length; ++i) {
                eor ^= (i ^ nums[i - 1]);
            }
            int diff = eor & (~eor + 1);
            int a = 0;
            for (int i = 1; i <= nums.length; ++i) {
                if ((nums[i - 1] & diff) == 0) {
                    a ^= nums[i - 1];
                }
                if ((i & diff) == 0) {
                    a ^= i;
                }
            }
            int b = eor ^ a;
            for (int num : nums) {
                if (a == num) {
                    return new int[] {a, b};
                }
            }
            return new int[] {b, a};
        }
    }
    
  • // OJ: https://leetcode.com/problems/set-mismatch
    // Time: O(N)
    // Space: O(N)
    class Solution {
    public:
        vector<int> findErrorNums(vector<int>& A) {
            unordered_map<int, int> m;
            for (auto n : A) m[n]++;
            int missing, dup;
            for (int i = 1; i <= A.size(); ++i) {
                if (!m.count(i)) missing = i;
                if (m[i] == 2) dup = i;
            }
            return { dup, missing };
        }
    };
    
  • class Solution:
        def findErrorNums(self, nums: List[int]) -> List[int]:
            eor, n = 0, len(nums)
            for i in range(1, n + 1):
                eor ^= i ^ nums[i - 1]
            diff = eor & (~eor + 1)
            a = 0
            for i in range(1, n + 1):
                if (nums[i - 1] & diff) == 0:
                    a ^= nums[i - 1]
                if (i & diff) == 0:
                    a ^= i
            b = eor ^ a
            for num in nums:
                if a == num:
                    return [a, b]
            return [b, a]
    
    ############
    
    class Solution(object):
      def findErrorNums(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        ans = [-1, -1]
        diff = diffSquare = 0
        for i, num in enumerate(nums):
          diff += i + 1 - num
          diffSquare += (i + 1) ** 2 - num ** 2
        ans[1] = (diffSquare / diff + diff) / 2
        ans[0] = ans[1] - diff
        ans.sort()
        if diff > 0:
          return ans
        return ans[::-1]
    
    
  • func findErrorNums(nums []int) []int {
    	n := len(nums)
    	for i := 0; i < n; i++ {
    		for nums[i] != i+1 && nums[nums[i]-1] != nums[i] {
    			nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i]
    		}
    	}
    	for i := 0; i < n; i++ {
    		if nums[i] != i+1 {
    			return []int{nums[i], i + 1}
    		}
    	}
    	return []int{-1, -1}
    }
    
    
  • function findErrorNums(nums: number[]): number[] {
        let xor = 0;
        for (let i = 0; i < nums.length; ++i) {
            xor ^= (i + 1) ^ nums[i];
        }
    
        let divide = 1;
        while ((xor & divide) == 0) {
            divide <<= 1;
        }
    
        let ans1 = 0,
            ans2 = 0;
        for (let i = 0; i < nums.length; ++i) {
            let cur = nums[i];
            if (divide & cur) {
                ans1 ^= cur;
            } else {
                ans2 ^= cur;
            }
    
            let idx = i + 1;
            if (divide & idx) {
                ans1 ^= idx;
            } else {
                ans2 ^= idx;
            }
        }
        return nums.includes(ans1) ? [ans1, ans2] : [ans2, ans1];
    }
    
    

All Problems

All Solutions