Missing And Repeating

Given an unsorted array arr of of positive integers. One number ‘A‘ from set {1, 2,….,n} is missing and one number ‘B‘ occurs twice in array. Find numbers A and B.

Examples

Input: arr[] = [2, 2]
Output: 2 1
Explanation: Repeating number is 2 and smallest positive missing number is 1.

Input: arr[] = [1, 3, 3] 
Output: 3 2
Explanation: Repeating number is 3 and smallest positive missing number is 2.

Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)

Constraints:
2 ≤ n ≤ 10⁵
1 ≤ arr[i] ≤ n

Approach 01:

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <set>

using namespace std;

class Solution {
public:
    vector<int> findTwoElements(vector<int>& arr) {
        const int MOD = 1e9 + 7;  // Define a large prime number for modulus
        sort(arr.begin(), arr.end());
        unordered_map<int, int> elementFrequency;
        int totalNumbers = arr.size();
        vector<int> result;

        // Calculate the missing number using the sum formula for the first N natural numbers (mod MOD)
        long long sumOfUniqueNumbers = 0;
        set<int> uniqueNumbers(arr.begin(), arr.end());
        for (int num : uniqueNumbers) {
            sumOfUniqueNumbers = (sumOfUniqueNumbers + num) % MOD;
        }

        long long expectedSum = ((long long)totalNumbers * (totalNumbers + 1) / 2) % MOD;
        int missingNumber = (expectedSum - sumOfUniqueNumbers + MOD) % MOD;

        // Count frequency of each number in the array
        for (int num : arr) {
            elementFrequency[num]++;
        }

        // Find the repeating number (the number with frequency 2)
        for (const auto& pair : elementFrequency) {
            if (pair.second == 2) {
                result.push_back(pair.first);  // Access the key (number) using pair.first
                break;
            }
        }

        // Add the missing number to the result
        result.push_back(missingNumber);

        return result;
    }
};

import collections

class Solution:
    def findTwoElement(self, arr):
        MOD = 10**9 + 7  # Define a large prime number for modulus
        arr.sort()
        elementFrequency = collections.Counter(arr)
        totalNumbers = len(arr)
        result = []
        
        # Calculate the missing number using the sum formula for the first N natural numbers (mod MOD)
        uniqueNumbers = set(arr)
        sumOfUniqueNumbers = sum(uniqueNumbers) % MOD
        expectedSum = (totalNumbers * (totalNumbers + 1) // 2) % MOD
        missingNumber = (expectedSum - sumOfUniqueNumbers + MOD) % MOD
        
        # Find the repeating number (the number with frequency 2)
        for number, frequency in elementFrequency.items():
            if frequency == 2:
                result.append(number)
                break
                
        # Add the missing number to the result
        result.append(missingNumber)
        
        return result

Time Complexity

• Sorting the Array:

  Sorting the array takes \(O(n \log n)\), where \(n\) is the size of the array arr.

• Calculating the Sum of Unique Numbers:

  Iterating over the set of unique numbers takes \(O(n)\), as inserting elements into the set and iterating through them is linear with respect to the number of unique elements.

• Counting Frequencies of Elements:

  Iterating over the array to count element frequencies takes \(O(n)\) since each element in the array is processed once.

• Finding the Repeating Number:

  Iterating through the frequency map to find the repeating number takes \(O(n)\), as the unordered map stores the frequency of each number in the array.

• Overall Time Complexity:

  The overall time complexity is dominated by the sorting step, so the total complexity is \(O(n \log n)\).

Space Complexity

• Auxiliary Space:

  The space complexity includes:

  • The space used by the unordered_map for frequency counting, which takes \(O(n)\) space.
  • The set for storing unique numbers, which also takes \(O(n)\) space.
  • Additional variables like result and other constants use \(O(1)\) space.
• Overall Space Complexity:

  The overall space complexity is \(O(n)\), primarily due to the space used by the unordered_map and set.