Missing Number

In this approach, we will create an array of integers ‘nums’, by converting each string present in list ‘binaryNums’ in the integers they represent.

A binary string can be converted into a respective integer by simply traversing from rightmost character (least significant bit) to leftmost character (most significant bit) and for each position of set bit i.e (index where char is ‘1’) we add the power of 2 according to its position in the result. 

Let’s name the method that does this conversion be convertToInt(binStr), where ‘binStr’ is the binary string whose integer equivalent is needed to be determined, then it can be implemented as follows:

• Initialize an integer variable num: = 0.
• Run a loop where ‘i’ ranges from len - 1 to 0 (where len is the length of ‘binStr’) and for reach ‘i’ do the following -:
  • If  binStr[i] =’ 1’,  do num += 2 ^ (len - i - 1).
• Return ‘num’.

We can convert any integer to binary by repeatedly dividing it by 2. Let’s name the method that converts an integer to binary string be convertToBin(num), where ‘num’ is the integer which we convert into a binary string,  then it can be implemented as follows:

• Create an empty string ‘binStr’.
• If ‘num’ = 0 then return “0”.
• Run a loop till ‘num’ > 0 and in each iteration do the following -:
  • If ‘num’ is odd then append ‘1’ in ‘binStr’ otherwise append ‘0’ in ‘binStr’.
  • Do num: = num / 2.
• Reverse ‘binStr’ and then return it.

 

Algorithm

• Create an integer array ‘nums’.
• Run a loop where ‘i’ ranges from 0 to N - 1 and for each ‘i’ do the following -:
  • Convert binaryNums[i] in integer using method convertToInt() as described above and add it in array nums.
• Sort nums in ascending order.
• Initialize an integer variable ‘missingNum’ := N.
• Run a loop where ‘i’ ranges from ‘0’ to N - 1, and if for any ‘i’ nums[i] != ‘i’, then assign missingNum’: = i and break the loop.
• Convert missingNum to the binary string using method convertToBin() as described above and return this binary string.

In this approach, we will create a boolean array ‘present’ of size ‘N + 1’, where present[i] will be true, only if the binary representation of integer ‘i’ is present in the list binaryNums. 

We can fill the boolean array ‘present’ by simply traversing over the list binaryNums and convert each string present in it using method convertToInt() defined in the previous approach, and mark the corresponding index true. In the end, only one index remains false, which will be the missing integer.

Algorithm

• Create a boolean array ‘present’ of size ‘N’ + 1.
• Run a loop where ‘i’ ranges from 0 to N - 1 and for each ‘i’ do the following -:
  • Convert binaryNums[i] in integer using method convertToInt() as described in Approach - 1
  • Let ‘num’ be the integer represented by  binaryNums[i], then do present[num]:= true
• Initialize an integer variable ‘missingNum’: = -1.
• Run a loop where ‘i’ ranges from ‘0’ to ‘N’, and if for any ‘i’ present[i] = false, then assign missingNum’:= i and break the loop.
• Convert missingNum to the binary string using method convertToBin() as described in the Approach - 1 and return this binary string

Let ‘xorAll’ be the bitwise xor of all the integers from 0 to ‘N’ and ‘xorNum’ be the bitwise xor of all the integers represented by the strings in the list binaryNums. Then missing integer will be xorAll ^ xorNum, where ^ is the bitwise xor operator.

Algorithm

• Initialize two integer variable ‘xorAll’: = 0 and ‘xorNum’: = 0.
• Run a loop where ‘i’ ranges from 0 to N and for each ‘i’ do xorAll:= xorAll ^ i
• Run a loop where ‘i’ ranges from 0 to N - 1 and for each ‘i’ do the following -:
  • Convert binaryNums[i] in integer using method convertToInt() as described in Approach - 1
  • Let ‘num’ be the integer represented by binaryNums[i], then do xorNum:= xorNum ^ num.
• Initialize an integer variable ‘missingNum’:= xorAll ^ xorNum .
• Convert missingNum to the binary string using method convertToBin() as described above and return this binary string

The number of bits required to represent an integer ‘N’ will be floor(logN) + 1 (log on base 2).

You can observe that number of integers between 0 to N (inclusive) that have the 0th-bit set will be floor((N + 1)/2).   

The number of integers between 0 to N (inclusive) that have the 1st-bit set will be  2 * floor((N + 1)/4) + max(0, (N + 1) % 4 - 2)   

The number of integers between 0 to N (inclusive) that have the 2nd-bit set will be  4 * floor((N + 1) / 8) + max(0, (N + 1) % 8 - 4)

In general, we can say that number of integers between 0 to N (inclusive that have ith bit-set will be  2 ^ i * floor((N + 1) / 2 ^ (i + 1)) + max(0, (N + 1) % 2 ^ (i + 1) - 2 ^ i).   

Algorithm

• Initialize an integer variable totalBits:= floor(logN) + 1.
• Create an empty string ‘missingNum’
• Run a loop where ‘i’ ranges from 0 to totalBits - 1, and for each ‘i’ do the following -:
  • Initialize an integer variable countReq: =  2 ^ i * floor((N + 1) / 2 ^ (i + 1)) + max(0, (N + 1) % 2 ^ (i + 1)  -  2 ^ i).
  • Initialize another integer variable count:= 0.
  • Run a loop where ‘j’ ranges from 0 to N - 1 and for each ‘j’ do the following -:
    • Let len = binaryNums[j].length
    • If len > i and binaryNums[j][len - i - 1] = ‘1’, then increment count by 1.
  • If count != countReq, then append ‘1’ in ‘missingNum’ otherwise append ‘0’ in ‘missingNum’.
• Reverse ‘missingNum’ and remove all leading ‘0’s.
• Return ‘missingNum’.