Set Mismatch Problem

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:

C++

#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;
}

Java

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

Output

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)

Contact Us