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 [duplicate, missing].

Examples

Example 1:

Input: nums = [1,2,2,4]
Output: [2,3]
Explanation: 2 is duplicated, 3 is missing.

Example 2:

Input: nums = [1,1]
Output: [1,2]
Explanation: 1 is duplicated, 2 is missing.

Constraints

  • 2 <= nums.length <= 10^4
  • 1 <= nums[i] <= 10^4
  • Exactly one number appears twice, exactly one is missing.

Thinking Process

  1. Mathematical Approach: Elegant solution using sum and square sum differences
  • Clarify if the array is sorted, has negatives, or allows duplicates.
  • Prefix sums answer range queries; hash maps answer pair/count queries.
  • In-place tricks use swap/write index instead of extra arrays.
Bit manipulation 1 0 1 1 0 1 0 XOR pairs · masks · shifts

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Prefix sum (this problem) O(n) O(n) Range queries, subarray sum
Sort + scan O(n log n) O(1) Intervals, meeting rooms
Kadane’s algorithm O(n) O(1) Maximum subarray
Hash map counting O(n) O(n) Frequency, two-sum variants

Solution

class Solution:
    def findErrorNums(self, nums):
        N = len(nums)

        x = 0
        y = 0

        for i in range(1, N + 1):
            x += nums[i - 1] - i
            y += nums[i - 1] * nums[i - 1] - i * i

        missing = (y // x + x) // 2
        duplicate = missing + x

        return [duplicate, missing]

Solution Explanation

Approach: Prefix sum (this problem)

Key idea: 1. Mathematical Approach: Elegant solution using sum and square sum differences

How the code works:

  1. Mathematical Approach: Elegant solution using sum and square sum differences
    • Clarify if the array is sorted, has negatives, or allows duplicates.
    • Prefix sums answer range queries; hash maps answer pair/count queries.
    • In-place tricks use swap/write index instead of extra arrays.

Walkthrough — input nums = [1,2,2,4], expected output [2,3]:

2 is duplicated, 3 is missing.

Common Mistakes

  1. Smallest input: nums = [1,1] → [1,2]
  2. Largest input: nums = [1,2,3,...,n-1,n,n] → [n, n+1] (but n+1 > n, so invalid)
  3. Duplicate at start: nums = [2,2,3,4] → [2,1]
  4. Duplicate at end: nums = [1,2,3,3] → [3,4] (but 4 > 3, so invalid)
  5. Missing at start: nums = [2,2,3,4] → [2,1]

  6. Missing at end: nums = [1,1,2,3] → [1,4] (but 4 > 3, so invalid)

  7. Integer overflow: Not using long long for square calculations
  8. Index off-by-one: Confusing 0-based vs 1-based indexing
  9. Sign errors: Incorrect handling of negative values in mathematical approach
  10. Division by zero: Not checking if x == 0 (shouldn’t happen per constraints)
  11. Wrong order: Returning [missing, duplicate] instead of [duplicate, missing]

Key Takeaways

  1. Mathematical Approach: Elegant solution using sum and square sum differences
  2. Negative Marking: Space-efficient in-place solution
  3. Hash Map: Simple and intuitive, uses extra space
  4. XOR: Bit manipulation approach, more complex but interesting

References

Template Reference