Assume that you have an array A[0.. n–1] which contains n integers from 0 to n i
ID: 3840599 • Letter: A
Question
Assume that you have an array A[0.. n–1] which contains n integers from 0 to n in the increasing order. Because the size of the array is n, one integer in the range from 0 to n is missing. For the problem, you have to design an efficient algorithm to find the missing integer. For example, let’s assume that the array A has eight elements such as 0, 1, 2, 3, 4, 5, 7, and 8. For the array A, your algorithm should return 6 as the missing integer number.
(a) Assume that your algorithm receives the array A and the array size n as input arguments. Describe the basic idea of your algorithm in English clearly.
(b) Based on the basic idea of (a), write a pseudocode of your algorithm. If your writing is not clear enough for the instructor to read/understand it, you will not get the credit.
(c) From your pseudocode presented at the question (b), present the basic operation.
(d) Present the time complexity of your algorithm using the O notation
Explanation / Answer
Please find my algorithm and let me know in case of any issue.
Algorithm: Using XOR
1) XOR all the array elements, let the result of XOR be X1.
2) XOR all numbers from 1 to n, let XOR be X2.
3) XOR of X1 and X2 gives the missing number.
/* getMissingNo takes array and size of array as arguments*/
int getMissingNo(int a[], int n)
{
int i;
int x1 = a[0]; /* For xor of all the elements in array */
int x2 = 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);
}
Time Complexity: O(N)