Question

Consider the following problem:

Input: a list of n-1 integers and these integers are in the range of 1 to n. There are no duplicates in list. One of the integers from 1 to n is missing in the list.

Output: find the missing integer

Let the input array be [2, 4, 1, 6, 3, 7, 8]. Elements in this list are in the range of 1 to 8. There are no duplicates, and 5 is missing. Your algorithm needs to return 5.

Let the input array be [6, 3, 4, 5, 1]. Elements in this list are in the range of 1 to 6. There are no duplicates, and 2 is missing. Your algorithm needs to return 2.

Design an algorithm that solves this problem.

Note: You need to consider all the possibilities including overflow.

Note: There is NO requirement of “in-place” algorithms. You can use extra memory/data structure in the algorithm.

(i) describe the idea behind your algorithm in English;

(ii) provide pseudocode;

Answer 1

We can solve this using xor concept

• We know that xor of two same numbers will be 0,and xor of different numbers is different
• If we xor all the elements given we have xored n-1 elements,again xor the result with integers from 1 to n total of n elements .
• n-1 given elements are present in 1 to n
• During the xor all the similar numbers will become 0 expect 1 which is the missing number
• the missing number doesn't become 0 because it has no partner i.e no same number
• We dont get any overflow with this method

code:

missingNO(int a[], int n)
{
int i;
int xor1 = a[0]; /* For xor of all the elements in array */
int xor2 = 1; /* For xor of all the elements from 1 to n+1 */
  
for (i = 1; i< n; i++)
x1 = x1^a[i];

for ( i = 2; i <= n+1; i++)
x2 = x2^i;

return (x1^x2);
}

If you are satisfied please upvote or if you have any doubts mention them in comments