*This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful,* *please like**this post and/or* *upvote**my solution post on Leetcode's forums.*

**Note**: This is my second version of a solution for this problem. Though I consider the first version 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

####
*Description:*

*Description:*

(*Jump to*: *Solution Idea* || *Code*: *JavaScript* | *Python* | *Java* | *C++*)

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 inrepetition of onenumber andloss of anothernumber.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:*

*Examples:*

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

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

####
*Constraints:*

*Constraints:*

`2 <= nums.length <= 10^4`

`1 <= nums[i] <= 10^4`

####
*Idea:*

*Idea:*

(*Jump to*: *Problem Description* || *Code*: *JavaScript* | *Python* | *Java* | *C++*)

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:*

*Implementation:*

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

####
*Javascript Code:*

*Javascript Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
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:*

*Python Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
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:*

*Java Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
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:*

*C++ Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
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;
}
};
```

## Top comments (4)

Interesting, but given the constraints isn't this as simple as just looping through an ordered array until we get a number that isn't it's index + 1 and then checking if the before value is the same? As there can only ever be one digit incorrect and it must be one higher or one lower than the digit that is replaced?

Or did I miss some key part of the question as I am terrible at these sorts of things lol!

If I am correct then the beauty of this is a single loop that exits the second it finds a match so it should be computationally efficient.

But you're assuming that the input array (

nums) is sorted; the problem description doesn't state that. And sorting it first would make the solutionO(N * log N)instead of justO(N).It can be a bit hard to explain, but each element of the solution posted here tells us two things...

but about different numbers. One number is the actual value of the element, the other is the number that is equal to theindexof the element plus1.So if we reach the end, for example, and see that

nums[5] = 20002, then we know that the number6(i = 5soi + 1 = 6) was seen twice,notthe number2. And yet we still preserved our ability to read the number2in this element with20002 % 10000.That's important because we'll be modifying the elements out of order in our first pass, and don't want to screw up our ability to properly read each number later on in the pass.

So in other words, in the first pass we're reading

numsati, but we're modifyingnumsatnums[i]. That's because we're treatingnumsvery much like we would its own "seen" or "visited" array. We just don't want those two purposes fornumsto impact each other, so we just... overlayanotherlevel of meaning onto the values stored innums.It's very much similar to using bit manipulation to combine two pieces of data into one.

This is why I am rubbish at these problems, I forget that

`.sort`

is expensive!I get it entirely now and thanks for taking the time to give such a detailed explanation!

No worries, and thanks for the question!