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.

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.

OR

Given a sequence of positive numbers less than equal to N, where one number is repeated and another is missing.

Examples

Example 1:

1
2
3
4

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

Example 2:

1
2
3
4

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

Solution

Method 1 – Using Sums and Sum of Squares (Mathematical Approach)

Intuition

Let x be the missing number and y be the repeated number. The sum of the first n natural numbers and the sum of their squares can be used to form two equations:

  • S = sum(nums) (sum of all elements in the array)
  • S1 = sum(x*x for x in nums) (sum of squares of all elements in the array)
  • a = n * (n + 1) / 2 (expected sum of 1 to n)
  • b = n * (n + 1) * (2n + 1) / 6 (expected sum of squares of 1 to n)

We have:

  • a = S + x - y
  • b = S1 + x^2 - y^2
  • So, x + y = (b - S1) / (a - S)
  • Now, with two equations and two variables, both x and y can be found.

Approach

  1. Compute the sum and sum of squares of the array.
  2. Compute the expected sum and sum of squares for numbers 1 to n.
  3. Use the two equations to solve for the missing and duplicate numbers.

Complexity

  • ⏰ Time complexity: O(n) — We traverse the array once to compute the sums, and all other operations are constant time.
  • 🧺 Space complexity: O(1) — Only a fixed number of variables are used for computation.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    std::vector<int> findErrorNums(std::vector<int>& nums) {
        long long n = nums.size();
        long long S = 0, S1 = 0;
        for (auto x : nums) {
            S += x;
            S1 += 1LL * x * x;
        }
        long long a = n * (n + 1) / 2;
        long long b = n * (n + 1) * (2 * n + 1) / 6;
        long long diff = a - S; // x - y
        long long sum = (b - S1) / diff; // x + y
        int x = (diff + sum) / 2;
        int y = sum - x;
        return {y, x}; // [duplicate, missing]
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func findErrorNums(nums []int) []int {
    n := len(nums)
    S, S1 := 0, 0
    for _, x := range nums {
        S += x
        S1 += x * x
    }
    a := n * (n + 1) / 2
    b := n * (n + 1) * (2*n + 1) / 6
    diff := a - S // x - y
    sum := (b - S1) / diff // x + y
    x := (diff + sum) / 2
    y := sum - x
    return []int{y, x} // [duplicate, missing]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public int[] findErrorNums(int[] nums) {
        int n = nums.length;
        long S = 0, S1 = 0;
        for (int x : nums) {
            S += x;
            S1 += 1L * x * x;
        }
        long a = n * (n + 1) / 2;
        long b = n * (n + 1) * (2 * n + 1) / 6;
        long diff = a - S; // x - y
        long sum = (b - S1) / diff; // x + y
        int x = (int)((diff + sum) / 2);
        int y = (int)(sum - x);
        return new int[]{y, x}; // [duplicate, missing]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def findErrorNums(self, nums: list[int]) -> list[int]:
        n = len(nums)
        S = sum(nums)
        S1 = sum(x*x for x in nums)
        a = n * (n + 1) // 2
        b = n * (n + 1) * (2 * n + 1) // 6
        diff = a - S  # x - y
        sum_ = (b - S1) // diff  # x + y
        x = (diff + sum_) // 2
        y = sum_ - x
        return [y, x]  # [duplicate, missing]

Method 2 – Cyclic Sort for Detecting Duplicate and Missing Number

Intuition

Since the numbers are in the range [1, n], we can use the array indices to place each number at its correct position (i.e., value v at index v-1). If a number is already at its correct position or a duplicate is found, we skip it. After sorting, the index where the value does not match the index + 1 gives us the duplicate and missing numbers.

Approach

  1. Iterate through the array and for each index i, while nums[i] != nums[nums[i] - 1], swap nums[i] with nums[nums[i] - 1].
  2. After the swaps, iterate through the array again. If nums[i] != i + 1, then nums[i] is the duplicate and i + 1 is the missing number.
  3. Return [duplicate, missing].

Complexity

  • ⏰ Time complexity: O(n), as each element is swapped at most once.
  • 🧺 Space complexity: O(1), since the algorithm works in-place and uses only a result array for output.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            while (nums[i] != nums[nums[i] - 1]) {
                swap(nums[i], nums[nums[i] - 1]);
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] != i + 1) return {nums[i], i + 1};
        }
        return {};
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func findErrorNums(nums []int) []int {
    n := len(nums)
    for i := 0; i < n; i++ {
        for nums[i] != nums[nums[i]-1] {
            nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i]
        }
    }
    for i := 0; i < n; i++ {
        if nums[i] != i+1 {
            return []int{nums[i], i+1}
        }
    }
    return []int{}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public int[] findErrorNums(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            while (nums[i] != nums[nums[i] - 1]) {
                int tmp = nums[i];
                nums[i] = nums[tmp - 1];
                nums[tmp - 1] = tmp;
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) return new int[]{nums[i], i + 1};
        }
        return new int[0];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def findErrorNums(self, nums: list[int]) -> list[int]:
        n = len(nums)
        for i in range(n):
            while nums[i] != nums[nums[i] - 1]:
                nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
        for i, v in enumerate(nums):
            if v != i + 1:
                return [v, i + 1]
        return []
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun findErrorNums(nums: IntArray): IntArray {
        val n = nums.size
        for (i in 0 until n) {
            while (nums[i] != nums[nums[i] - 1]) {
                val tmp = nums[i]
                nums[i] = nums[tmp - 1]
                nums[tmp - 1] = tmp
            }
        }
        for (i in 0 until n) {
            if (nums[i] != i + 1) return intArrayOf(nums[i], i + 1)
        }
        return intArrayOf()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

function findErrorNums(nums: number[]): number[] {
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        while (nums[i] !== nums[nums[i] - 1]) {
            const tmp = nums[i];
            nums[i] = nums[tmp - 1];
            nums[tmp - 1] = tmp;
        }
    }
    for (let i = 0; i < n; i++) {
        if (nums[i] !== i + 1) return [nums[i], i + 1];
    }
    return [];
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

impl Solution {
    pub fn find_error_nums(nums: &mut Vec<i32>) -> Vec<i32> {
        let n = nums.len();
        for i in 0..n {
            while nums[i] != nums[(nums[i] - 1) as usize] {
                let j = (nums[i] - 1) as usize;
                nums.swap(i, j);
            }
        }
        for (i, &v) in nums.iter().enumerate() {
            if v != (i as i32) + 1 {
                return vec![v, (i as i32) + 1];
            }
        }
        vec![]
    }
}