DIsgin & analysis algorth course Remarks: In all the algorithms, always explain

Question

DIsgin & analysis algorth course    

Remarks: In all the algorithms, always explain their correctness and analyze their com-
plexity. The complexity should be as small as possible. A correct algorithm with large
complexity, may not get full credit.

----------------------------------------------------------------------

Question 3: Given an array A of size n - 2 that contains all the numbers 1, n except for
two. Give an algorithm to find the two missing numbers. Use a constant extra space
(namely apart from the array, only a constant number of variables).

Explanation / Answer

Hi, Please find my algorithm:

Below are steps.

Find XOR of all array elements and natural numbers from 1 to n. Let the array be arr[] = {1, 3, 5, 6}
XOR = (1 ^ 3 ^ 5 ^ 6) ^ (1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6)
As per the property of XOR, same elements will cancel out and we will be left with 2 XOR 4 = 6 (110). But we don’t know the exact numbers,let them be X and Y.
A bit is set in xor only if corresponding bits in X and Y are different. This is the crucial step to understand.
We take a set bit in XOR. Let us consider the rightmost set bit in XOR, set_bit_no = 010
Now again if we XOR all the elements of arr[] and 1 to n that have rightmost bit set we will get one of the repeating numbers, say x.
Ex: Elements in arr[] with bit set: {3, 6}
Elements from 1 to n with bit set {2, 3, 6}
Result of XOR'ing all these is x = 2.
Similarly, if we XOR all the elements of arr[] and 1 to n that have rightmost bit not set, we will get the other element, say y.
Ex: Elements in arr[] with bit not set: {1, 5}
Elements from 1 to n with bit not set {1, 4, 5}
Result of XOR'ing all these is y = 4

void findTwoMissingNumbers(int arr[], int n)
{
/* Get the XOR of all elements in arr[] and
{1, 2 .. n} */
int XOR = arr[0];
for (int i = 1; i < n-2; i++)
XOR ^= arr[i];
for (int i = 1; i <= n; i++)
XOR ^= i;

// Now XOR has XOR of two missing elements. Any set
// bit in it must be set in one missing and unset in
// other missing number

// Get a set bit of XOR (We get the rightmost set bit)
int set_bit_no = XOR & ~(XOR-1);

// Now divide elements in two sets by comparing rightmost
// set bit of XOR with bit at same position in each element.
int x = 0, y = 0; // Initialize missing numbers
for (int i = 0; i < n-2; i++)
{
if (arr[i] & set_bit_no)
x = x ^ arr[i]; /*XOR of first set in arr[] */
else
y = y ^ arr[i]; /*XOR of second set in arr[] */
}
for (int i = 1; i <= n; i++)
{
if (i & set_bit_no)
x = x ^ i; /* XOR of first set in arr[] and
{1, 2, ...n }*/
else
y = y ^ i; /* XOR of second set in arr[] and
{1, 2, ...n } */
}

printf("Two Missing Numbers are %d %d", x, y);
}

Time Complexity : O(n)
Auxiliary Space : O(1)

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.