# Set Mismatch
**Difficulty:** EASY
[External](https://leetcode.com/problems/set-mismatch)
Canonical: https://scaleengineer.com/dsa/problems/set-mismatch
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table
**Companies:** [Grammarly](https://scaleengineer.com/companies/grammarly)
---
## 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_.

**Example 1:**

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

**Example 2:**

**Input:** nums = [1,1]
**Output:** [1,2]

**Constraints:**

* `2 <= nums.length <= 104`
* `1 <= nums[i] <= 104`

# Approaches
## Brute Force
This is the most straightforward and intuitive approach. We can iterate through all numbers from 1 to `n` (where `n` is the length of the array). For each number, we perform another iteration through the input array `nums` to count its occurrences.
**Time:** O(n^2), where n is the number of elements in the `nums` array. The outer loop runs `n` times, and for each iteration, the inner loop also runs `n` times. · **Space:** O(1), as we only use a few constant extra variables to store the result and the counter.
**Pros:** Simple to understand and implement.; Requires no extra space, aside from the result array.
**Cons:** Extremely inefficient with a time complexity of O(n^2).; Will likely result in a 'Time Limit Exceeded' error on most online judges for larger inputs.
### Explanation
The method involves a nested loop structure. The outer loop iterates through each number `i` that is expected to be in the set, from 1 to `n`. For each of these numbers, the inner loop traverses the entire `nums` array to count how many times `i` appears. By the definition of the problem, one number will appear twice (its count will be 2), and one number will not appear at all (its count will be 0). We use two variables, `duplicate` and `missing`, to keep track of these numbers as we find them. After checking all numbers from 1 to `n`, we will have identified both the duplicate and the missing value.

```java
class Solution {
    public int[] findErrorNums(int[] nums) {
        int n = nums.length;
        int duplicate = -1;
        int missing = -1;
        for (int i = 1; i <= n; i++) {
            int count = 0;
            for (int num : nums) {
                if (num == i) {
                    count++;
                }
            }
            if (count == 2) {
                duplicate = i;
            } else if (count == 0) {
                missing = i;
            }
        }
        return new int[]{duplicate, missing};
    }
}
```
### Algorithm
- Get the size of the array, `n`.
- Initialize `duplicate = -1` and `missing = -1`.
- Loop `i` from 1 to `n`.
- Inside the loop, initialize a counter `count = 0`.
- Start an inner loop through each `num` in the `nums` array.
- If `num == i`, increment `count`.
- After the inner loop finishes, check the value of `count`.
- If `count == 2`, it means `i` is the duplicated number, so set `duplicate = i`.
- If `count == 0`, it means `i` is the missing number, so set `missing = i`.
- After the outer loop finishes, return the array `[duplicate, missing]`.

## Using a Hash Map
A more efficient approach involves trading space for time. We can use a hash map (or a frequency array, since the numbers are within a specific range) to count the occurrences of each number in the input array. This eliminates the need for the costly nested loop.
**Time:** O(n). We iterate through the `nums` array once to build the map and then iterate from 1 to `n` once to find the result. This is O(n + n) = O(n). · **Space:** O(n), as the hash map can store up to `n-1` key-value pairs in the worst case.
**Pros:** Significantly more efficient than the brute-force approach with a linear time complexity.; The logic is straightforward and easy to follow.
**Cons:** Requires extra space proportional to the number of unique elements in the array, which can be O(n).
### Explanation
First, we traverse the `nums` array once, populating a hash map where keys are the numbers from the array and values are their frequencies. This gives us a count of each number in O(n) time. 

Next, we iterate through the numbers from 1 to `n`. For each number `i`, we query the hash map. If the map indicates that the frequency of `i` is 2, we have found our duplicate. If the map does not contain the key `i`, it means `i` was never present in the input array, making it the missing number. This second loop also takes O(n) time, leading to an overall linear time complexity.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int[] findErrorNums(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        int duplicate = -1;
        int missing = -1;
        int n = nums.length;

        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        for (int i = 1; i <= n; i++) {
            if (map.containsKey(i)) {
                if (map.get(i) == 2) {
                    duplicate = i;
                }
            } else {
                missing = i;
            }
        }
        return new int[]{duplicate, missing};
    }
}
```
### Algorithm
- Create a `HashMap<Integer, Integer>` to store the frequency of each number.
- Iterate through the input array `nums`. For each `num`, update its count in the hash map.
- Initialize `duplicate = -1` and `missing = -1`.
- Get the size of the array, `n`.
- Iterate from `i = 1` to `n`.
- For each `i`, check its presence and count in the hash map.
- If `map.get(i)` is 2, then `i` is the duplicate number.
- If `map.get(i)` is null (or the key `i` does not exist), then `i` is the missing number.
- Return the `[duplicate, missing]` array.

## In-place Marking with Negation
A highly efficient approach with optimal time and space complexity involves using the input array itself as a data structure to track seen numbers. Since the numbers are in the range `[1, n]`, we can map each number `k` to the array index `k-1`. We mark a number as 'seen' by negating the value at its corresponding index.
**Time:** O(n), as we perform two separate, non-nested passes over the array. · **Space:** O(1), as we modify the array in-place and use only a few extra variables for the results.
**Pros:** Optimal time complexity of O(n).; Optimal space complexity of O(1).; It's an in-place algorithm.
**Cons:** This approach modifies the input array. If the input must be preserved, a copy must be made first, which would negate the O(1) space advantage.
### Explanation
We perform two passes over the array. In the first pass, we iterate through each number `num` in `nums`. For each `num`, we find its corresponding index `index = abs(num) - 1`. If the value at `nums[index]` is already negative, we know that we've encountered `abs(num)` before, so it must be the duplicate. If `nums[index]` is positive, we flip its sign to negative to mark `abs(num)` as seen.

After this first pass, exactly one number from 1 to `n` will not have been used to negate an index: the missing number. Therefore, in a second pass, we iterate from `i = 0` to `n-1`. The index `i` for which `nums[i]` is still positive tells us that the number `i+1` was the one that was missing from the set.

```java
class Solution {
    public int[] findErrorNums(int[] nums) {
        int duplicate = -1;
        int missing = -1;
        for (int num : nums) {
            int index = Math.abs(num) - 1;
            if (nums[index] < 0) {
                duplicate = Math.abs(num);
            } else {
                nums[index] *= -1;
            }
        }

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                missing = i + 1;
                break; 
            }
        }
        return new int[]{duplicate, missing};
    }
}
```
### Algorithm
- Initialize `duplicate = -1` and `missing = -1`.
- Iterate through the `nums` array. For each `num`:
  - Calculate the corresponding index: `index = Math.abs(num) - 1`.
  - Check the sign of the element at this index, `nums[index]`.
  - If `nums[index]` is negative, it means the number `Math.abs(num)` has been seen before. This is our duplicate. Store it in the `duplicate` variable.
  - If `nums[index]` is positive, negate it (`nums[index] *= -1`) to mark that we have now seen the number `Math.abs(num)`.
- After the first pass, the duplicate is found. Now, find the missing number.
- Iterate through the modified `nums` array from `i = 0` to `n-1`.
- The first index `i` where the element `nums[i]` is still positive corresponds to the missing number, `i + 1`. Store this in the `missing` variable and break the loop.
- Return `[duplicate, missing]`.

## Constant Space Solution using Math
This elegant approach leverages mathematical formulas to find the duplicate and missing numbers in linear time and constant space, without modifying the input array. It's based on comparing the sum and the sum of squares of the expected set `(1..n)` with the actual set `nums`.
**Time:** O(n), as it involves a single pass through the array to compute the sums. · **Space:** O(1), as it only requires a few variables to store the calculated sums.
**Pros:** Optimal time complexity of O(n).; Optimal space complexity of O(1).; Does not modify the input array, making it a pure function.
**Cons:** The sum of squares can become very large, potentially causing integer overflow if not handled with 64-bit integers (long in Java).; The logic is less direct compared to other methods.
### Explanation
Let the duplicate number be `x` and the missing number be `y`. We can establish two independent equations involving `x` and `y`.

1.  **Sum Difference**: The sum of the numbers in `nums` will be `(Sum of 1..n) - y + x`. Therefore, `(Sum of nums) - (Sum of 1..n) = x - y`.
2.  **Sum of Squares Difference**: Similarly, the sum of the squares of numbers in `nums` will be `(Sum of squares of 1..n) - y^2 + x^2`. Therefore, `(Sum of squares of nums) - (Sum of squares of 1..n) = x^2 - y^2`.

We know that `x^2 - y^2 = (x - y)(x + y)`. We can find `(x - y)` from the first equation, which allows us to solve for `(x + y)`. Now we have a simple system of two linear equations:
- `x - y = A`
- `x + y = B`

Solving this system gives us `x = (A+B)/2` and `y = (B-A)/2`. It's crucial to use 64-bit integers (`long`) for the sum calculations to prevent overflow, as `n` can be up to 10,000.

```java
class Solution {
    public int[] findErrorNums(int[] nums) {
        int n = nums.length;
        long n_long = n;
        
        long expectedSum = n_long * (n_long + 1) / 2;
        long expectedSumSq = n_long * (n_long + 1) * (2 * n_long + 1) / 6;
        
        long actualSum = 0;
        long actualSumSq = 0;
        
        for (int num : nums) {
            actualSum += num;
            actualSumSq += (long)num * num;
        }
        
        long sumDiff = actualSum - expectedSum; // duplicate - missing
        long sumSqDiff = actualSumSq - expectedSumSq; // duplicate^2 - missing^2
        
        long sumXY = sumSqDiff / sumDiff; // duplicate + missing
        
        int duplicate = (int)((sumXY + sumDiff) / 2);
        int missing = (int)((sumXY - sumDiff) / 2);
        
        return new int[]{duplicate, missing};
    }
}
```
### Algorithm
- Get the size of the array, `n`.
- Calculate the expected sum of numbers from 1 to `n`: `expectedSum = n * (n + 1) / 2`.
- Calculate the expected sum of squares from 1 to `n`: `expectedSumSq = n * (n + 1) * (2n + 1) / 6`.
- Initialize `actualSum = 0` and `actualSumSq = 0`.
- Iterate through the `nums` array, calculating the actual sum and sum of squares of its elements.
- Find the difference between actual and expected sums: `sumDiff = actualSum - expectedSum`. This equals `duplicate - missing`.
- Find the difference between actual and expected sums of squares: `sumSqDiff = actualSumSq - expectedSumSq`. This equals `duplicate^2 - missing^2`.
- Calculate `sumXY = sumSqDiff / sumDiff`. This equals `duplicate + missing`.
- Solve the two simultaneous equations:
  - `duplicate = (sumXY + sumDiff) / 2`
  - `missing = (sumXY - sumDiff) / 2`
- Return `[duplicate, missing]`.

# Solutions
### Java

```java
class Solution {
public
  int[] findErrorNums(int[] nums) {
    int n = nums.length;
    int xs = 0;
    for (int i = 1; i <= n; ++i) {
      xs ^= i ^ nums[i - 1];
    }
    int lb = xs & -xs;
    int a = 0;
    for (int i = 1; i <= n; ++i) {
      if ((i & lb) > 0) {
        a ^= i;
      }
      if ((nums[i - 1] & lb) > 0) {
        a ^= nums[i - 1];
      }
    }
    int b = xs ^ a;
    for (int i = 0; i < n; ++i) {
      if (nums[i] == a) {
        return new int[]{a, b};
      }
    }
    return new int[]{b, a};
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> findErrorNums(vector<int> &nums) {
    int n = nums.size();
    int xs = 0;
    for (int i = 1; i <= n; ++i) {
      xs ^= i ^ nums[i - 1];
    }
    int lb = xs & -xs;
    int a = 0;
    for (int i = 1; i <= n; ++i) {
      if (i & lb) {
        a ^= i;
      }
      if (nums[i - 1] & lb) {
        a ^= nums[i - 1];
      }
    }
    int b = xs ^ a;
    for (int i = 0; i < n; ++i) {
      if (nums[i] == a) {
        return {a, b};
      }
    }
    return {b, a};
  }
};

```

### Python

```python
class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]: xs = 0 for i, x in enumerate(nums, 1): xs ^= i ^ x a = 0 lb = xs & - xs for i, x in enumerate(nums, 1): if i & lb: a ^= i if x & lb: a ^= x b = xs ^ a for x in nums: if x == a: return [a, b] return [b, a]

```