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. We must write a program to find the missing and duplicate numbers. For eg:
Int a[] = {1,2,3,4,6,7,8,9,10,4};
As you can see in above example, missing number is “5” and duplicate number is “4”.
Method 1 — Without using extra memory
Algorithm
- Iterate through each element in the array.
- For every element “I” in array
- If value at a[i] is “-1”. Then “I” is the duplicate value.
- Else a[a[i]] = -1
- Iterate again through each element in array.
- Whichever index value is not “-1” is the missing value.
Let’s have a look at the program to solve above problem.
#define MAX_ARRAY_SIZE 500
void print_missing_and_duplicate (int missing, int duplicate)
{
int arr[MAX_ARRAY_SIZE] = {0};
/* creating the array with missing and duplicate value */
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;
}
}
Method 2 — Using a separate array
Algorithm
- Define a new array “count” of same length and initialize it with 0.
- Iterate through every element in the input array.
- Increment value in count array as count[arr[i]] += 1
- Iterate through every element in count array.
- Whichever index value is “0” is missing value.
- Whichever index value is higher than “1” is duplicate value.
Let’s have a look at the program to solve the problem.
void print_missing_and_duplicate_version2 (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;
}
}
Let’s have a look at the main function which uses above function.
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_version2 (33, 77);
print_missing_and_duplicate_version2 (10, 30);
}
Let’s look at 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
