You have a set of integers nums that contains integers from 1 to n. However, there is one duplicate number and one missing number in the set. Return an array containing the duplicate number and the missing number.
Table of Contents
Sample Input and Expected Output:
Input:
nums = [1, 2, 2, 4]
Output:
The duplicate number is: 2
The missing number is: 3
Input:
nums = [3, 2, 3, 4, 6, 5]
Output:
The duplicate number is: 3
The missing number is: 1
Set Mismatch Solution in C++:
The idea is to use the array itself as a hash table. We traverse the array and for each number x, we negate the value at index abs(x) - 1 to mark its presence. We also keep track of the duplicate number when we encounter a negative value. After processing all numbers, the missing number will be the index with a positive value, and the duplicate number will be the index that was already marked as negative.
#include <iostream>
#include <vector>
#include <cmath>
std::vector<int> findErrorNums(std::vector<int>& nums) {
std::vector<int> result(2);
for (int num : nums) {
int index = std::abs(num) - 1; // Convert num to index (zero-based).
if (nums[index] > 0) {
nums[index] = -nums[index]; // Mark presence of num by negating the value at index.
} else {
result[0] = index + 1; // If the value at index is negative, it's a duplicate.
}
}
for (int i = 0; i < nums.size(); i++) {
if (nums[i] > 0) {
result[1] = i + 1; // If the value at index is positive, it's the missing number.
break;
}
}
return result;
}
int main() {
std::vector<int> nums1 = {1, 2, 2, 4};
std::vector<int> nums2 = {3, 2, 3, 4, 6, 5};
std::vector<int> result1 = findErrorNums(nums1);
std::vector<int> result2 = findErrorNums(nums2);
std::cout << "The duplicate number is: " << result1[0] << std::endl;
std::cout << "The missing number is: " << result1[1] << std::endl;
std::cout << "The duplicate number is: " << result2[0] << std::endl;
std::cout << "The missing number is: " << result2[1] << std::endl;
return 0;
}
Set Mismatch: Time Complexity and Space Complexity:
The time complexity of the solution is O(n), where n is the size of the input vector nums. Each number is processed once in the array.
The space complexity is O(1) as we are using a constant amount of additional space for variables in the solution, regardless of the size of the input array. The algorithm is performed in-place without using any extra data structures. The result vector contains only two elements, so it can be considered as constant space.