Given an integer array arr[], which originally contains all the numbers from 1 to n. Due to some error, one of the numbers in arr[] got duplicated to another number in arr[], which results in repetition of one number and loss of another number. Find the number that occurs twice and the number that is missing and return them as an array.

Examples:

Input: arr[] = {1, 2, 2, 4}
Output: {2, 3}
Explanation: The number 2 appears twice, and the number 3 is missing.

Input: arr = {1, 1}
Output: {1, 2}
Explanation: The number 1 appears twice, and the number 2 is missing.

Approach: To solve the problem, follow the below idea:

The idea is to identify the duplicated number and the missing number in the array. We can achieve this by utilizing a frequency array. By iterating through the array, we can keep track of the numbers seen and determine which number is duplicated and which one is missing. The element which has frequency = 2 is the duplicate element and the element which has frequency = 0 is the missing number.

Step-by-step-approach:

• Create a frequency array or map to count occurrences of each number.
• Iterate through the input array and count the occurrences of each number.
• Iterate through the range from 1 to n and check the frequency of each number
• The number with a frequency of 2 is the duplicate.
• The number with a frequency of 0 is the missing number.
• Return the duplicate and missing numbers in an array.

Below is the implementation of the algorithm:

#include <bits/stdc++.h>
using namespace std;

vector<int> findErrorNums(vector<int>& arr) {
    int n = arr.size();
    unordered_map<int, int> count;
    int duplicate, missing;

    // Count frequencies of each number
    for (int num : arr) {
        count[num]++;
    }

    // Find the duplicate and missing numbers
    for (int i = 1; i <= n; i++) {
        if (count[i] == 2) {
            duplicate = i;
        } else if (count[i] == 0) {
            missing = i;
        }
    }

    return {duplicate, missing};
}

// Driver code
int main() {
    vector<int> arr1 = {1, 2, 2, 4};
    vector<int> result1 = findErrorNums(arr1);
    cout << "Duplicate: " << result1[0] << ", Missing: " << result1[1] << endl;

    vector<int> arr2 = {1, 1};
    vector<int> result2 = findErrorNums(arr2);
    cout << "Duplicate: " << result2[0] << ", Missing: " << result2[1] << endl;

    return 0;
}

import java.util.*;

public class Main {
    public static int[] findErrorNums(int[] arr) {
        int n = arr.length;
        Map<Integer, Integer> count = new HashMap<>();
        int duplicate = 0, missing = 0;

        // Count frequencies of each number
        for (int num : arr) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }

        // Find the duplicate and missing numbers
        for (int i = 1; i <= n; i++) {
            if (count.getOrDefault(i, 0) == 2) {
                duplicate = i;
            } else if (count.getOrDefault(i, 0) == 0) {
                missing = i;
            }
        }

        return new int[]{duplicate, missing};
    }

    public static void main(String[] args) {
        int[] arr1 = {1, 2, 2, 4};
        int[] result1 = findErrorNums(arr1);
        System.out.println("Duplicate: " + result1[0] + ", Missing: " + result1[1]);

        int[] arr2 = {1, 1};
        int[] result2 = findErrorNums(arr2);
        System.out.println("Duplicate: " + result2[0] + ", Missing: " + result2[1]);
    }
}


// This code is contributed by Shivam Gupta

Duplicate: 2, Missing: 3
Duplicate: 1, Missing: 2

Time Complexity: O(n), where n is the length of the input array
Auxiliary Space: O(n)

Approach 2: Using Mathematical Method

The approach described is known as the Mathematical Method or Summation Method. This method use the properties of the sum of the first n natural numbers and the sum of their squares to identify the duplicate and missing numbers without using extra space for a frequency array or map.

Step-by-step Approach:

• Calculate the expected sum of the first n natural numbers.
• Calculate the expected sum of the squares of the first n natural numbers.
• Compute the actual sum and sum of squares from the given array.
• Find the differences between the expected and actual sums and sums of squares.
• Use these differences to solve for the missing and duplicate numbers.

Below is the implementation of the algorithm:

#include <cmath>
#include <iostream>
#include <vector>

using namespace std;

vector<int> findErrorNums(vector<int>& arr)
{
    int n = arr.size();
    long long S_n = n * (n + 1) / 2;
    long long S_n2 = n * (n + 1) * (2 * n + 1) / 6;

    long long S_arr = 0, S_arr2 = 0;
    for (int num : arr) {
        S_arr += num;
        S_arr2 += (long long)num * num;
    }

    long long diff1 = S_n - S_arr;
    long long diff2 = S_n2 - S_arr2;

    long long sum_xy = diff2 / diff1;

    int missing = (diff1 + sum_xy) / 2;
    int duplicate = missing - diff1;

    return { duplicate, missing };
}

// Driver code
int main()
{
    vector<int> arr1 = { 1, 2, 2, 4 };
    vector<int> result1 = findErrorNums(arr1);
    cout << "Duplicate: " << result1[0]
         << ", Missing: " << result1[1] << endl;

    vector<int> arr2 = { 1, 1 };
    vector<int> result2 = findErrorNums(arr2);
    cout << "Duplicate: " << result2[0]
         << ", Missing: " << result2[1] << endl;

    return 0;
}

import java.util.Arrays;

public class SetMismatch {
    public static int[] findErrorNums(int[] arr)
    {
        int n = arr.length;
        long S_n = n * (n + 1) / 2;
        long S_n2 = n * (n + 1) * (2 * n + 1) / 6;

        long S_arr = 0, S_arr2 = 0;
        for (int num : arr) {
            S_arr += num;
            S_arr2 += (long)num * num;
        }

        long diff1 = S_n - S_arr;
        long diff2 = S_n2 - S_arr2;

        long sum_xy = diff2 / diff1;

        int missing = (int)((diff1 + sum_xy) / 2);
        int duplicate = (int)(missing - diff1);

        return new int[] { duplicate, missing };
    }

    public static void main(String[] args)
    {
        int[] arr1 = { 1, 2, 2, 4 };
        System.out.println(
            "Duplicate: " + findErrorNums(arr1)[0]
            + ", Missing: " + findErrorNums(arr1)[1]);

        int[] arr2 = { 1, 1 };
        System.out.println(
            "Duplicate: " + findErrorNums(arr2)[0]
            + ", Missing: " + findErrorNums(arr2)[1]);
    }
}

def find_error_nums(arr):
    n = len(arr)
    S_n = n * (n + 1) // 2
    S_n2 = n * (n + 1) * (2 * n + 1) // 6

    S_arr = sum(arr)
    S_arr2 = sum(x * x for x in arr)

    diff1 = S_n - S_arr
    diff2 = S_n2 - S_arr2

    sum_xy = diff2 // diff1

    missing = (diff1 + sum_xy) // 2
    duplicate = missing - diff1

    return [duplicate, missing]


# Driver code
arr1 = [1, 2, 2, 4]
print("Duplicate:", find_error_nums(arr1)[
      0], ", Missing:", find_error_nums(arr1)[1])

arr2 = [1, 1]
print("Duplicate:", find_error_nums(arr2)[
      0], ", Missing:", find_error_nums(arr2)[1])

function findErrorNums(arr)
{
    const n = arr.length;
    const S_n = n * (n + 1) / 2;
    const S_n2 = n * (n + 1) * (2 * n + 1) / 6;

    let S_arr = 0, S_arr2 = 0;
    for (let num of arr) {
        S_arr += num;
        S_arr2 += num * num;
    }

    const diff1 = S_n - S_arr;
    const diff2 = S_n2 - S_arr2;

    const sum_xy = diff2 / diff1;

    const missing = (diff1 + sum_xy) / 2;
    const duplicate = missing - diff1;

    return [ duplicate, missing ];
}

// Driver code
const arr1 = [ 1, 2, 2, 4 ];
console.log(
    `Duplicate: ${findErrorNums(arr1)[0]}, Missing: ${
        findErrorNums(arr1)[1]}`);

const arr2 = [ 1, 1 ];
console.log(
    `Duplicate: ${findErrorNums(arr2)[0]}, Missing: ${
        findErrorNums(arr2)[1]}`);

Duplicate: 2, Missing: 3
Duplicate: 1, Missing: 2

Time Complexity: O(n), as we are iterating through the array twice.
Auxiliary Space: O(1), as we are using a constant amount of extra space.