by Given an unsorted array of size n. Array elements are in range from 1 to n.
One number from set {1, 2, …n} is missing and one number occurs twice in array.
Find these two numbers.
For example:
Input arr = [1,3,4,5,6,7,4]
Missing Item = 2
Duplicate Item = 4
Solution Using Space Complexity O(n) and Time Complexity O(n)
In this solution, we will use a count array which will store the count of occurrence of every number.
Algorithm
- Define a count array of size n with initialized value of 0.
- Traverse the input array and increment the count array as count[arr[i]] += 1
- Traverse the count array.
- if value is 0 then that index is the missing number in the array.
- If value is 2 then that index is the duplicate number in the array.
Let’s have a look into the sample code.
void print_missing_and_duplicate_using_count (int missing, int duplicate)
{
int arr[MAX_ARRAY_SIZE] = {0};
for (int i = 0; i < MAX_ARRAY_SIZE; i++)
{
if (i == missing)
arr[i] = duplicate;
else
arr[i] = i;
}
int count[MAX_ARRAY_SIZE] = {0};
for (int i = 0; i < MAX_ARRAY_SIZE; i++)
{
count[arr[i]] += 1;
}
for (int i = 0; i < MAX_ARRAY_SIZE; i++)
{
if (count[i] == 0)
cout << "Missing Number in the list is: " << i << endl;
else if (count[i] == 2)
cout << "Duplicate item in the list is: " << i << endl;
}
}
Solution Using Space Complexity O(1) and Time Complexity O(n)
In this solution, we will utilize the existing array memory to find the missing and duplicate both numbers.
Algorithm
- Traverse the input array.
- use absolute value of every element as index and set the value to “-1” which will act as visited node.
- If the value is already “-1” then that index is the duplicate item in the array.
- Traverse the array again.
- Index at which value is not “-1” is the missing item in the array.
Let’s have a look into the sample code.
void print_missing_and_duplicate (int missing, int duplicate)
{
int arr[MAX_ARRAY_SIZE] = {0};
for (int i = 0; i < MAX_ARRAY_SIZE; i++)
{
if (i == missing)
arr[i] = duplicate;
else
arr[i] = i;
}
for (int i = 0; i < MAX_ARRAY_SIZE; i++)
{
if (arr[i] < 0)
{
cout << "Duplicate item in the list is: " << i << endl;
}
else
{
arr[arr[i]] = -1;
}
}
for (int i = 0; i < MAX_ARRAY_SIZE; i++)
{
if (arr[i] >= 0)
cout << "Missing Number in the list is: " << i << endl;
}
}
Let’s look into a main function which utilizes both the functions.
int main ()
{
print_missing_and_duplicate (30, 60);
print_missing_and_duplicate (15, 60);
print_missing_and_duplicate (10, 30);
print_missing_and_duplicate (33, 77);
print_missing_and_duplicate_using_count (33, 77);
print_missing_and_duplicate_using_count (10, 30);
}
Let’s analyze the output of above main function.
Duplicate item in the list is: 60
Missing Number in the list is: 30
Duplicate item in the list is: 60
Missing Number in the list is: 15
Duplicate item in the list is: 30
Missing Number in the list is: 10
Duplicate item in the list is: 77
Missing Number in the list is: 33
Missing Number in the list is: 33
Duplicate item in the list is: 77
Missing Number in the list is: 10
Duplicate item in the list is: 30
