Missing Number

Moderate
0/80
Average time to solve is 30m
17 upvotes
Asked in companies
HSBCSterlite Technologies LimitedSamsung

Problem statement

You are given an array/list ‘BINARYNUMS’ that consists of ‘N’ distinct strings which represent all integers from 0 to N in binary representation except one integer. This integer between 0 to ‘N’ whose binary representation is not present in list ‘BINARYNUMS’ is called ‘Missing Integer’.

Your task is to find the binary representation of that ‘Missing Integer’. You should return a string that represents this ‘Missing Integer’ in binary without leading zeros.

Note

1. There will be no leading zeros in any string in the list ‘BINARYNUMS’.

Example:

Consider N = 5 and the list ‘binaryNums’=  [“0”, “01”, “010”, “100”, “101”].  This list consists of the binary representation of numbers [0, 1, 2, 4, 5]. Clearly, the missing number is 3 and its binary representation will be “11”. So you should return string “11”.
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line of input contains an integer ‘T’ denoting the number of test cases. then ‘T’ test cases follow.

The first line contains single integers ‘N’ represent the size of the list ‘BINARYNUMS’.

The second line contains ‘N’ space-separated string representing the list ‘BINARYNUMS’.
Output format : 
For each test case, print a single line containing a single string that represents this ‘Missing Integer’ in binary without leading zeros.

The output of each test case will be printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 50
1 <= N <= 10 ^ 4

Where ‘T’ is the total number of test cases and ‘N’ is the size of list ‘BINARYNUMS’

Time limit: 1 sec.
Sample Input 1:
2
1
1
5
0 01 010 100 101
Sample Output 1:
0
11
Explanation of Sample Input 1:
Test case 1:
There is only one string in ‘BINARYNUMS’ and that is “1”, which represents integer 1. Clearly, Missing Integer is 0, and its binary representation is also “0”.       

Test case 2:
See the problem statement for an explanation.
Sample Input 2:
2
3
0 10 11
8
0 1 10 11 100 101 110 111
Sample Output 2:
1
1000
Hint

Can sorting help?

Approaches (4)
Convert to integers (Sorting)

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.
Time Complexity

O(N * log(N)), where ‘N’ is the size of the given list binaryNums.

 

Converting any integer ‘X’ in binary or converting binary representation of any integer ‘X’ to its corresponding integer both takes O(log(X)) times. In this approach, we convert the ‘N’ binary string that represents integers upto ‘N’ to their respective integers. That will takes O(N * log(N)) times. Sorting an integer array of size ‘N’ will also take O(N * log(N)) times. Thus overall complexity will be O(N * log(N)) + O(N * log(N)) = O(N * log(N))

Space Complexity

O(N), where ‘N’ is the size of the given list binaryNums.

 

The size of the array nums is of the order of O(N). Thus overall space complexity will also be O(N).

Code Solution
(100% EXP penalty)
Missing Number
Full screen
Console