Consider an array A containing all but two of the integers between 0 and (2^n) -
ID: 3851681 • Letter: C
Question
Consider an array A containing all but two of the integers between 0 and (2^n) -1 (inclusive). Your only access to the array is with the following function, which you may assume to take constant time.
Provide and (asymptotically) analyze the fastest pseudocode you can for determining which number is missing from the array.
2 eparam ii The element of the array 3 eparam ij The index of the bit of Aliij 4 requires 0 ll,JJ 5 Creturns the ij-th least significant bit of Alii] 6 example if AC3] 17, then fetch(3,4) and fetch (3,0) should both return 1 8 l int fetc (int ii, int jj);Explanation / Answer
This can be done by summing the array and then finding sum of missing number (we know number are from 0 to 2^n - 1). (Please note even if we have fetch function we can still find value of each array element by calling fetch constant number of times for each bit value)
Now one number has to be less than avg and other greater than avergae as two number are distinctive
First missing number can be computed by sim of natural number from 1 to avg - sum of all array element smaller than avg.
Second missing number as sum of natural numbers from avg+1 to 2^n -1 minus the sum of array elements greater than than avg
As this is performing sum only hence it will be O(number of array element).