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 ≤ 105
1 ≤ arr[i] ≤ n
Approach 01:
-
C++
-
Python
#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.
- The space used by the
- Overall Space Complexity:
The overall space complexity is \(O(n)\), primarily due to the space used by the
unordered_map
andset
.