Solution: Set Mismatch (ver. 2)
Tags: algorithms, javascript, java, python
Published: 2021-03-02 12:01:23

*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 second version of a solution for this problem. Though I consider [the first version](https://dev.to/seanpgallivan/solution-set-mismatch-4ejh) a less complex solution more appropriate for an "Easy" problem, this post 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))

In order to solve this problem with **O(1)** extra space, we can use **nums** directly to keep track of which numbers have been seen so far. To do so, we need to be able to modify the elements of **nums** in such a way as to be easily able to obtain the original value again.

One of the easiest ways to do this is with the use of the **mod** operator (**%**). Since the largest value **nums[i]** is **10^4**, we can use that number as our base. By adding **10^4** to the value of an element, it can now tell us two things: the original value of the element (**num % 10^4**) and whether or not the number equal to the index has been seen (**num > 10^4**).

Since the values in nums are **1-indexed** and nums itself is **0-indexed**, however, we'll have to shift the mod function to **(nums - 1) % 10^4**.

If we iterate through **nums** and apply this addition, then at the end, we'll know that the value that was seen twice will be **> 20000** and the number that was never seen is **< 10001**.

So we just have to iterate through **nums** a second time, check for these values, add them to our answer (**ans**), and then **return ans**.

---

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

There are very few differences between the four languages for this solution.

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
var findErrorNums = function(nums) {
    let N = nums.length, ans = [,]
    for (let i = 0; i < N; i++)
        nums[(nums[i] - 1) % 10000] += 10000
    for (let i = 0; i < N; i++)
        if (nums[i] > 20000) ans[0] = i + 1
        else if (nums[i] < 10001) ans[1] = i + 1
    return ans
};
```

---

#### ***Python Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
class Solution:
    def findErrorNums(self, nums):
        ans = [0,0]
        for num in nums:
            nums[(num - 1) % 10000] += 10000
        for i in range(len(nums)):
            if nums[i] > 20000: ans[0] = i + 1
            elif nums[i] < 10001: ans[1] = i + 1
        return ans
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
class Solution {
    public int[] findErrorNums(int[] nums) {
        int N = nums.length;
        int[] ans = new int[2];
        for (int num : nums)
            nums[(num - 1) % 10000] += 10000;
        for (int i = 0; i < N; i++)
            if (nums[i] > 20000) ans[0] = i + 1;
            else if (nums[i] < 10001) ans[1] = i + 1;
        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();
        vector<int> ans(2);
        for (int num : nums)
            nums[(num - 1) % 10000] += 10000;
        for (int i = 0; i < N; i++)
            if (nums[i] > 20000) ans[0] = i + 1;
            else if (nums[i] < 10001) ans[1] = i + 1;
        return ans;
    }
};
```