Reference: LeetCode EPI 11.10

Difficulty: Easy

My Post: [Super Java Collection] Brute-Force, HashMap+Count, HashSet+Math, Bitwise (clever), Sorting

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

1 | Input: nums = [1,2,2,4] |

## Analysis

### Brute-Force

For each value from `1`

to `n`

, count its occurrence in `nums`

.

1 | public int[] findErrorNums(int[] nums) { |

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

### Map + Count

**Note:** Break the loop when `dup`

and `miss`

are all set.

1 | public int[] findErrorNums(int[] nums) { |

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

### Set + Math

See the example for how this method works.

1 | // actual: 1 + 2 + 4 = 7 (use a hash set to remove extra duplicates) |

So `expected`

- `actual`

= `miss`

. And `dup`

can be detected in the array iteration.

1 | public int[] findErrorNums(int[] nums) { |

### Bit Manipulation (XOR)

**No Extra Space!**

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

1 | // 1 2 3 4 5 (expected) |

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

1 | // 1 2 3 4 5 |

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

1 | public int[] findErrorNums(int[] nums) { |

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

1 | public int[] findErrorNums(int[] nums) { |

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