Problem -
An array A contains all the integers from Oto n, except for one number which
is missing. In this problem, we cannot access an entire integer in A with a single operation. The
elements of A are represented in binary, and the only operation we can use to access them is "fetch
the jth bit of A[ i ],"which takes constant time. Write code to find the missing integer. Can you do
it in O(n) time?
Solution -
BITWISE XOR
00000000 0
00000001 1
00000010 11
00000011 0
00000100 100
00000101 1
00000110 111
00000111 0
00001000 1000
00001001 1
00001010 1011
00001011 0
00001100 1100
00001101 1
00001110 1111
00001111 0
00010000 10000
If BITWISE XOR is performed on all numbers from 0 to n then
- if n%4 == 0 then BITWISE_XOR(0,n) = n
- if n%4 == 1 then BITWISE_XOR(0,n) = 1
- if n%4 == 2 then BITWISE_XOR(0,n) = n+1
- if n%4 == 3 then BITWISE_XOR(0,n) = 0
Hence the missing number can be calculated by performing BITWISE_XOR on the computed BITWISE_XOR(0,n)
missing number = BITWISE_XOR ( BITWISE_XOR(given numbers), BITWISE_XOR(0,n))
BITWISE_XOR(0,n) - O(1)
BITWISE_XOR(given numbers) - O(n)
Hence the overall time complexity is O(n)
