Reference: LeetCode EPI 11.10
Difficulty: Easy

## Problem

The set S originally contains numbers from 1 to n. But unfortunately, due to the data error, one of the numbers in the set got duplicated to another number in the set, which results in repetition of one number and loss of another number.

Given an array nums representing the data status of this set after the error. Your task is to firstly find the number occurs twice and then find the number that is missing. Return them in the form of an array.

Note:

• The given array size will in the range [2, 10000].
• The given array’s numbers won’t have any order.

Example:

## Analysis

### Brute-Force

For each value from 1 to n, count its occurrence in nums.

Time: $O(N^2)$
Space: $O(1)$

### Map + Count

Note: Break the loop when dup and miss are all set.

Time: $O(N)$
Space: $O(N)$

### Set + Math

See the example for how this method works.

So expected - actual = miss. And dup can be detected in the array iteration.

### Bit Manipulation (XOR)

No Extra Space!

The idea is very clear. I should use an example to explain it.

Note: XOR: x ^ x = 0, x ^ y ^ x = y, x ^ y ^ x ^ x ^ y = x (remember this usage!)

First Pass: By doing XOR for each number above, xor would finally equals 2^3, which is miss^dup; however, we don’t know which is which!

Second Pass:

• Then we use xor & ~(xor - 1) to get the rightmost one-bit of xor. For example, if xor in binary is 00011010, the result is 00000010. We call it oneBit.
• Again, for each number above, if a number has that bit on, we put it to a set group; otherwise, throw it to unset group.
• By doing XOR for set and unset groups, we would have setXor = 2 and unsetXor = 3; however, we don’t know which is which! T_T

Third Pass: Decide which is which :)

Time: $O(N)$
Space: $O(1)$

### Sorting

Not Recommended!

Check for corner cases: [1, 1], [2, 2], [1, 2, 2], [2, 2, 3]. We can reduce the corner case logic of miss to checking the first element and last element in the array.

• If the first element after sorting is not 1, then 1 is the missing element.
• If the last element after sorting is not n, then n is the missing element.

Time: $O(N\log{N})$
Space: $O(1)$

Comment Junhao Wang
Hi, I was a master student at USC studying Computer Science.