Consider an array A containing all but two of the integers between 0 and 2n-1. (

Question

Consider an array A containing all but two of the integers between 0 and 2n-1. (inclusive). For technical reasons, 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

Problem is to find two missing numbers in the array of [0, 2n - 1].

Let's take an example when only one number is missing from the array of [0, 2n - 1]. for n = 2, we have below array

A = [0,1,3]

we can use the xor property here

a xor a = 0

a xor 0 = a

so we xor all elements from [0,3] with our array A such that the existing element crosses each other and only missing element remains

[0,1,2,3] xor [0,1,3]

^ ==> is xor operator

=> (0^0) ^ (1^1) ^ (2) ^ (3^3)

=> 0 ^ 0 ^ 2 ^ 0

=> 2

therefore 2 is the missing element in the array.

what if two numbers are missing from the above array?

let's take the same array as above but this time along with 2 1 was also missing.

A = [0,3]

can xor as previous help ?? let's see

[0,1,2,3] xor [0, 3]

==> (0^0) ^ (1) ^ (2) ^ (3^3)

==> 0 ^ 1 ^ 2 ^ 0

==> 1 ^ 2

==> 3

what can we observe about the result, that the result is xor of two missing number to be found?

3 = (1 ^ 2)

but how can we get 1and 2 from 3?

let's see 1, 2 and 3 in binary.

1 = 1(binary)

2 = 10(binary)

3 = 11(binary)

XOR TABLE

X    Y X ^ Y
0    0    0
0    1    1
1    0    1
1    1    0

if we see the above table the result is 1 only if either of them is 1(not both).

we can use this, so in our xor result if we see any position in binary is 1 that mean either(not both) of the missing also has one in the same position so we will divide both our array int two parts such that the element that has one in that binary position goes in one part and the element that has zero goes in other.

combined array [0,1,2,3] + [0 , 3] = [0,0,1,2,3,3]

dividing the array based on the xor result 3(11).

let's keep all element which has rightmost one in one array and other ones in different.

part1 = [0, 0, 2] this number does not have one in its rightmost position.

part2 = [1, 3, 3] this number have one in its rightmost position.

let's xor all element of array part1 == 0 ^ 0 ^ 2 = 2

let's xor all element of array part1 == 1 ^ 3 ^ 3 = 1

hence we get our result.

Pseudo Code:

function get_missing_two(A)

xor_result = 0

combined_array = []

for i from 0 to length(A) - 1

#xor with each element of array A

array_i_element = 0

for j from 0 to 31

xor_result = xor_result ^ fetch(i,j) of A

array_ith_element = array_ith_element | (1<< (fetch(i,j)) )

#xor with each elements from 0 to 2n - 1

xor_result = xor_result ^ i

combined_array.add(i)

combined_array.add(array_ith_element)

#find the first set bit of xor_result

set_bit = 31

for i from 0 to 31

#check if ith bit og xor_result is set

if ((xor_result & (1<<i) )! = 0)

set_bit = i

break

#divide combined array into 2 parts

part1 = []

part2 = []

for i from 0 to length(combined_array) - 1

#if ith element of combined array has bit set in its set_bit position add it to part1 array

if ((combined_array[i] & (1<<set_bit)) != 0)

part1.add(combined_array[i])

else

part2.add(combined_array[i])

missing_1 = 0

missing_2 = 0

for i from 0 to length(part1)

missing_1 = missing_1 ^ part1[i]

for i from 0 to length(part2)

missing_2 = missing_2 ^ part2[i]

return ( missing_1, missing_2 )

Time complexity = O(n * 32 ) => O(n)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---