645. Set Mismatch

Jump to Solution: Python Java C++ JavaScript C#

Problem Description

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.

Examples:

Example 1:

Input: nums = [1,2,2,4]
Output: [2,3]
Explanation: 2 appears twice and 3 is missing.

Example 2:

Input: nums = [1,1]
Output: [1,2]
Explanation: 1 appears twice and 2 is missing.

Constraints:

2 ≤ nums.length ≤ 10⁴
1 ≤ nums[i] ≤ 10⁴

Python Solution

class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        n = len(nums)
        count = [0] * (n + 1)
        
        # Count occurrences of each number
        for num in nums:
            count[num] += 1
        
        duplicate = missing = 0
        
        # Find duplicate and missing numbers
        for i in range(1, n + 1):
            if count[i] == 2:
                duplicate = i
            elif count[i] == 0:
                missing = i
        
        return [duplicate, missing]

Alternative Solution (Using XOR):

class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        # Get the XOR of all numbers from 1 to n and all numbers in nums
        xor_all = 0
        for i in range(len(nums)):
            xor_all ^= (i + 1) ^ nums[i]
        
        # Get the rightmost set bit in xor_all
        rightmost_set_bit = xor_all & -xor_all
        
        # Divide numbers into two groups based on rightmost set bit
        x = y = 0
        for i in range(len(nums)):
            if (i + 1) & rightmost_set_bit:
                x ^= i + 1
            if nums[i] & rightmost_set_bit:
                x ^= nums[i]
            else:
                y ^= nums[i]
            if not ((i + 1) & rightmost_set_bit):
                y ^= i + 1
        
        # Check which number appears twice
        for num in nums:
            if num == x:
                return [x, y]
        return [y, x]

Implementation Notes:

First solution uses counting approach with O(n) time and O(n) space
Second solution uses XOR for O(n) time and O(1) space
Both solutions handle all edge cases correctly

Java Solution

class Solution {
    public int[] findErrorNums(int[] nums) {
        int n = nums.length;
        int[] count = new int[n + 1];
        
        // Count occurrences of each number
        for (int num : nums) {
            count[num]++;
        }
        
        int[] result = new int[2];
        
        // Find duplicate and missing numbers
        for (int i = 1; i <= n; i++) {
            if (count[i] == 2) {
                result[0] = i;
            } else if (count[i] == 0) {
                result[1] = i;
            }
        }
        
        return result;
    }
}

C++ Solution

class Solution {
public:
    vector findErrorNums(vector& nums) {
        int n = nums.size();
        vector count(n + 1);
        
        // Count occurrences of each number
        for (int num : nums) {
            count[num]++;
        }
        
        vector result(2);
        
        // Find duplicate and missing numbers
        for (int i = 1; i <= n; i++) {
            if (count[i] == 2) {
                result[0] = i;
            } else if (count[i] == 0) {
                result[1] = i;
            }
        }
        
        return result;
    }
};

JavaScript Solution

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findErrorNums = function(nums) {
    const n = nums.length;
    const count = new Array(n + 1).fill(0);
    
    // Count occurrences of each number
    for (const num of nums) {
        count[num]++;
    }
    
    const result = [0, 0];
    
    // Find duplicate and missing numbers
    for (let i = 1; i <= n; i++) {
        if (count[i] === 2) {
            result[0] = i;
        } else if (count[i] === 0) {
            result[1] = i;
        }
    }
    
    return result;
};

C# Solution

public class Solution {
    public int[] FindErrorNums(int[] nums) {
        int n = nums.Length;
        int[] count = new int[n + 1];
        
        // Count occurrences of each number
        foreach (int num in nums) {
            count[num]++;
        }
        
        int[] result = new int[2];
        
        // Find duplicate and missing numbers
        for (int i = 1; i <= n; i++) {
            if (count[i] == 2) {
                result[0] = i;
            } else if (count[i] == 0) {
                result[1] = i;
            }
        }
        
        return result;
    }
}

Alternative Solution (Using LINQ):

public class Solution {
    public int[] FindErrorNums(int[] nums) {
        var n = nums.Length;
        var duplicate = nums.GroupBy(x => x)
                          .Where(g => g.Count() > 1)
                          .Select(g => g.Key)
                          .First();
        var missing = Enumerable.Range(1, n)
                              .Except(nums)
                              .First();
        return new[] { duplicate, missing };
    }
}

Implementation Notes:

First solution uses array counting for optimal performance
Second solution uses LINQ for cleaner but less efficient implementation
Both solutions handle all edge cases correctly