Solution: Set Mismatch (ver. 1)
Tags: algorithms, javascript, java, python
Published: 2021-03-02 09:35:32

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/set-mismatch/discuss/1089560).*

---

*__Note__: This is my first version of a solution for this problem. Though I consider this version to be a less complex solution more appropriate for an "Easy" problem, [my second solution version](https://dev.to/seanpgallivan/solution-set-mismatch-ver-2-218b) demonstrates how to achieve the solution with a space complexity of only O(1) extra space instead of O(N).*

---

#### [Leetcode Problem #645 (*Easy*): Set Mismatch](https://leetcode.com/problems/set-mismatch/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
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]
>
Example 2:||
|---:|---|
Input:|nums = [1,1]
Output:|[1,2]

---

#### ***Constraints:***
>
 - `2 <= nums.length <= 10^4`
 - `1 <= nums[i] <= 10^4`

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

For this problem, we can take advantage of some math, because one thing we know about a sequence of numbers from **1** to **N** is that their **sum** should equal the **N**th **triangular number** (**N * (N + 1) / 2**).

Since the only difference between the ideal array ranging from **1** to **N** and our input array **nums** is the duplicated number, that means that the difference between the **sum** of **nums** and the **N**th triangular number is the same as the difference between our duplicated number (**dupe**) and the missing number.

We can easily find the duplicated number by utilizing a boolean array (**seen**) to keep track of which numbers have already been seen. While iterating through **nums**, whenever we come across a number for the second time, that number must be our **dupe**. We can also use this iteration to find the difference in the sums.

Then we can just **return** the **dupe** and the **sum** difference applied to the **dupe** to identify the missing number.

---

#### ***Implementation:***

Javascript doesn't have a boolean array, so we can use the typed **Uint8Array()** as the closest stand-in. Python likewise doesn't have a boolean array, so we'll have to use a normal list.

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
var findErrorNums = function(nums) {
    let N = nums.length, dupe, sum = N * (N + 1) / 2,
        seen = new Uint8Array(N+1)
    for (let i = 0; i < N; i++) {
        let num = nums[i]
        sum -= num
        if (seen[num]) dupe = num
        seen[num]++
    }
    return [dupe, sum + dupe]
};
```

---

#### ***Python Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        N, dupe = len(nums), 0
        seen, sumN = [0] * (N+1), N * (N+1) // 2
        for num in nums:
            sumN -= num
            if seen[num]: dupe = num
            seen[num] += 1
        return [dupe, sumN + dupe]
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
class Solution {
    public int[] findErrorNums(int[] nums) {
        int N = nums.length, sum = N * (N + 1) / 2;
        int[] ans = new int[2];
        boolean[] seen = new boolean[N+1];
        for (int num : nums) {
            sum -= num;
            if (seen[num]) ans[0] = num;
            seen[num] = true;
        }
        ans[1] = sum + ans[0];
        return ans;
    }
}
```

---

#### ***C++ Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        int N = nums.size(), sum = N * (N + 1) / 2;
        vector<int> ans(2);
        vector<bool> seen(N+1);
        for (int num : nums) {
            sum -= num;
            if (seen[num]) ans[0] = num;
            seen[num] = true;
        }
        ans[1] = sum + ans[0];
        return ans;
    }
};
```