Question

Let be a permutation of {1,2,……n}.Let $\prod$ _-1 be the (n-1)-tuple with one element from $\prod$ missing.

TI

Alice shows Bob $\prod$ _-1[i] one by one in the increasing order of i from 1 to (n-1).bob’s task is to compute the missing element from $\prod$ _-1 that is in $\prod$ with very limited – O(log n) bits – of memory.

Design an algorithm to compute the missing element in this memory-limited and access-limited model, i.e Alice can only show each number to Bob once, and Bob can only use O(log n) bits of memory. Show that the algorithm is correct and give the time and memory complexity for this algorithm.e a permutation of {1,2,……n}.Let $\prod$ _-1 be the (n-1)-tuple with one element from pie missing.

Alice shows Bob $\prod$ _-1[i] one by one in the increasing order of i from 1 to (n-1).Bob’s task is to compute the missing element from _{$\prod$ -1} that is in $\prod$ with very limited
– O(log n) bits – of memory.

Design an algorithm to compute the missing element in this memory-limited and access-limited model, i.e Alice can only show each number to Bob once, and Bob can only use O(log n) bits of memory. Show that the algorithm is correct and give the time and memory complexity for this algorithm.

Answer 1

Considering n = 5.

Suppose $\prod$ is a perutation of P1(1,2,3,4,5), lets assume P1(2,3,1,5,4)

Suppose Alice shows him numbers from $\prod$ -1 , i.e. P2(2, 3, 5,1).

Now as we can see, Both P1 and P2 are sorted.. Alice will give one number at a time to Bob,

Now Notice that numbers range from 1 to n, to represent a number n in binary(which computer uses), we require log(n) bits.

Also, if we XOR the same numbers together, they will result in 0. While if we XOR number X with 0, result will be 0.

This gives us one clue, that if we combine both P1 and P2 together, there are 2n-1 numbers out of which 2n-2 numbers are in form of pairs(means two 1s, two 2s and so on.. ) there is just single number which is missing from P2 and that need to be find. So If XOR both P1 and P2 together, the pairs will eventually result in 0 (two 1s XOR together will result in 0) and 0 XORed with the number occurring just once in both P1 and P2 together and wil result in that same number, which will be our result..

Do notice that XOR will same amount of bits as any of the numbers itself.. and we already showed the maximum number can take log(n) bits..

So algorithm is to first find the XOR of all the numbers in $\prod$ . Lets store it in variable xor_result. Now as alice keeps giving the elements one by one.. Keep Updating the xor_result as
xor_result = xor_result XOR new_number

Once Alice is done with all the numbers, whatever is remaining in variable xor_result, is our answer.

Complexity: O(N) for finding the XOR of first list, as we need to visit each element.

Memory: log(n) bits