Problem 2 MUST be solved “in place”, i.e. you cannot use other arrays to copy pa

Question

Problem 2 MUST be solved “in place”, i.e. you cannot use other arrays to copy parts of the given array. You can use only a few extra variables

Use comments to explain well your “algorithms” to solve the given problem and an estimate of how many operations (such as comparisons, swaps, additions etc.) your algorithm performs.

Program 2: Find the missing number An unsorted integer array contains 98 different numbers from 1 to 100. So, among the numbers from 1 to 100, two distinct numbers are missing. Find them

Explanation / Answer

Algorithm:

STEP 1:
   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)

STEP 2:
   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.

STEP 3:
   A bit is set in xor only if corresponding bits in X and Y are different. This is the crucial step to understand.
STEP 4:
   We take a set bit in XOR. Let us consider the rightmost set bit in XOR, set_bit_no = 010
STEP 5:
   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.
STEP 6:
   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

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

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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