Set Mismatch — LeetCode 645 Python Solution

The problem

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.

Example

Input

nums = [1,2,2,4]

Output

[2,3]

Python solution

from typing import List

def findErrorNums(nums: List[int]) -> List[int]:
    n = len(nums)
    seen = set()
    dup = -1
    for x in nums:
        if x in seen:
            dup = x
        else:
            seen.add(x)
    missing = next(i for i in range(1, n + 1) if i not in seen)
    return [dup, missing]

Complexity

Pattern: Bit Manipulation

Use XOR, masks and the low-bit trick to replace whole data structures with an integer. LeetCode 645. Set Mismatch is filed here because LeetCode tags it Bit Manipulation, which is the vocabulary this hub collects.

The bit manipulation guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Related problems