Find the missing number in the duplicate array

Given two integer arrays where second array is duplicate of first array with just 1 element missing. Find the element.
Example:

Input:
Array1 – 9 7 8 5 4 6 2 3 1
Array2 – 2 4 3 9 1 8 5 6

Output:
7

Algorithm

Algorithm 1:
1. Iterate over array1, find sum of all numbers of array1, say result.
2. Iterate over array2 and subtract every element of array2 from result.
3. Print result.
Typically in an interview, there can be a follow-up question to solve this problem without using arithmetic operators. Following is the algorithm for the same.

Algorithm 2:
1. Initialize result = 0.
2. Iterate over both the input arrays and XOR ‘result’ with each element of the input arrays.
3. Print result.

Order of the Algorithm

Time Complexity is O(n)
Space Complexity is O(1)

 

Code->

#include <bits/stdc++.h>
using namespace std;

// This function mainly does XOR of all elements
// of arr1[] and arr2[]
void findMissing(int arr1[], int arr2[], int M,
int N)
{
if (M != N-1 && N != M-1)
{
cout << "Invalid Input";
return;
}

// Do XOR of all element
int res = 0;
for (int i=0; i<M; i++)
res = res^arr1[i];
for (int i=0; i<N; i++)
res = res^arr2[i];

cout << "Missing element is " << res;
}

// Driver Code
int main()
{
int arr1[] = {4, 1, 5, 9, 7};
int arr2[] = {7, 5, 9, 4};

int M = sizeof(arr1) / sizeof(int);
int N = sizeof(arr2) / sizeof(int);

findMissing(arr1, arr2, M, N);

return 0;
}

 

Leave a Reply

Your email address will not be published. Required fields are marked *

For Inserting code :
Paste your code in the comment form, select it and then click the language link

C | C++ | Java |

*