Missing Number
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”.

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

Question

Missing Number

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”.

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.

Accepted Answer

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.

Space Complexity: O(n)Explanation:

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).

Time Complexity: O(nlogn)Explanation:

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))

Java (SE 1.8)

/*

    Time Complexity : O(N * log(N))

    Space Complexity : O(N)



    Where N is the size of the given list binaryNums.

*/



import java.util.Collections;

import java.util.ArrayList;

    

public class Solution {

    public static String rev(String input){



        char[] temparray = input.toCharArray();

        int left, right = 0;

        right = temparray.length - 1;

 

        for (left = 0; left < right; left++, right--) {



            // Swap values of left and right.

            char temp = temparray[left];

            temparray[left] = temparray[right];

            temparray[right] = temp;

        }



        String res = "";

        for(char c : temparray) {

            res += c;

        }

        return res;

    }



    public static int convertToInt(String binStr) {

        // Length of given binary string.

        int len = binStr.length();



        int num = 0;



        /*

            Traversing from rightmost character (least significant bit) to 

            leftmost character (most significant bit).

        */

        for(int i = len - 1; i >= 0; i--) {

            if(binStr.charAt(i) == '1') {



                // Note-: (1 << i) = 2 ^ i.

                num += (1 << (len - i - 1));

            }

        }



        return num;

    }

    

    public static String convertToBin(int num) {

        String binStr = "";



        // Corner Case.

        if(num == 0) {

            return "0";

        }



        // Repeatedly divide 'num' by 2 to find binary representation of num.

        while(num > 0) {

            if(num % 2 == 1) {

                binStr += '1';

            }

            else {

                binStr += '0';

            }

            num = num / 2;

        }



        // Reverse 'binStr'.

        binStr = rev(binStr);



        return binStr;

    }

    

	public static String findMissingNumber(ArrayList binaryNums, int n){

        ArrayList nums = new ArrayList(n);



        // Convert all binary strings to integers.

        for(int i = 0; i < n; i++) {

            nums.add(i, convertToInt(binaryNums.get(i)));

        }



        // Sort 'nums' in ascending order. 

        Collections.sort(nums);  

        int missingNum = n;



        for(int i = 0; i < n; i++) {

            if(nums.get(i) != i) {

                missingNum = i;

                break;

            }

        }



        // Convert missingNum in binary and return it.

        return convertToBin(missingNum);

	}

}

Python (3.5)

'''

    Time Complexity : O(N * log(N))

    Space Complexity : O(N)



    Where ‘N’ is the size of the given list binaryNums.

'''



def convertToInt(binStr):



    # Length of given binary string.

    l = len(binStr)



    num = 0



    '''

        Traversing from rightmost character (least significant bit) to 

        leftmost character (most significant bit).

    '''

    for i in range(l - 1, -1, -1):

        if(binStr[i] == '1'):

            # Note-: (1 << i) = 2 ^ i.

            num += (1 << (l - i - 1))



    return num



def convertToBin(num):

    binStr = ""



    if(num == 0):

        return "0"



    # Repeatedly divide 'num' by 2 to find binary representation of num.

    while(num > 0):

        if(num & 1):

            binStr += '1'

        else:

            binStr += '0'



        num = num//2



    # Reverse 'binStr'.

    binStr = "".join(reversed(binStr))



    return binStr



def findMissingNumber(binaryNums, n):

    nums = [0 for i in range(n)]



    # Convert all binary strings to integers.

    for i in range(n):

        nums[i] = convertToInt(binaryNums[i])



    # Sort 'nums' in ascending order.

    nums.sort()

    missingNum = n



    for i in range(n):

        if(nums[i] != i):

            missingNum = i

            break



    # Convert missingNum in binary and return it.

    return convertToBin(missingNum)

C++ (g++ 5.4)

/*

    Time Complexity : O(N * log(N))

    Space Complexity : O(N)



    Where ‘N’ is the size of the given list binaryNums.

*/



#include 



int convertToInt(string binStr) 

{

    // Length of given binary string.

    int len = binStr.length();



    int num = 0;



    /*

        Traversing from rightmost character (least significant bit) to 

        leftmost character (most significant bit).

    */   

    for(int i = len - 1; i >= 0; i--) 

    {

        if(binStr[i] == '1') 

        {

            // Note-: (1 << i) = 2 ^ i.

            num += (1 << (len - i - 1));

        }

    }

    return num;

}



string convertToBin(int num) 

{

    string binStr;



    // Corner Case.

    if(num == 0) 

    {

        return "0";

    }



    // Repeatedly divide 'num' by 2 to find binary representation of num.

    while(num > 0) 

    {

        if(num & 1) 

        {

            binStr += '1';

        }

        else 

        {

            binStr += '0';

        }

        num = num / 2;

    }



    // Reverse 'binStr'.

    reverse(binStr.begin(), binStr.end());



    return binStr;

}



string findMissingNumber(vector &binaryNums, int n) 

{

    vector nums(n);

    

    // Convert all binary strings to integers.

    for(int i = 0; i < n; i++) 

    {

        nums[i] = convertToInt(binaryNums[i]);

    }



    // Sort 'nums' in ascending order. 

    sort(nums.begin(), nums.end());

    int missingNum = n;



    for(int i = 0; i < n; i++) 

    {

        if(nums[i] != i) 

        {

            missingNum = i;

            break;

        }

    }



    // Convert missingNum in binary and return it.

    return convertToBin(missingNum);

}

Accepted Answer

Convert to integers (Boolean Array)

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

Space Complexity: O(n)Explanation:

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

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

Time Complexity: O(nlogn)Explanation:

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. Iterating over the array ‘present’ takes O(N) times. Thus overall complexity will be O(N * log(N)) + O(N) = O(N * log(N))

Java (SE 1.8)

/*

    Time Complexity : O(N * log(N))

    Space Complexity : O(N)



    Where N is the size of the given list binaryNums.

*/



import java.util.ArrayList;

    

public class Solution {

    public static String rev(String input) {



        char[] temparray = input.toCharArray();

        int left, right = 0;

        right = temparray.length - 1;

 

        for (left = 0; left < right; left++, right--) {



            // Swap values of left and right.

            char temp = temparray[left];

            temparray[left] = temparray[right];

            temparray[right] = temp;

        }

        String res = "";

        for(char c : temparray) {

            res += c;

        }

        return res;

    }



    public static int convertToInt(String binStr) {



        // Length of given binary string.

        int len = binStr.length();



        int num = 0;



        /*

            Traversing from rightmost character (least significant bit) to

            leftmost character (most significant bit).

        */

        for(int i = len - 1; i >= 0; i--) {

            if(binStr.charAt(i) == '1') {



                // Note-: (1 << i) = 2 ^ i.

                num += (1 << (len - i - 1));

            }

        }

        return num;

    }

    

    public static String convertToBin(int num) {

        String binStr = "";



        // Corner Case.

        if(num == 0) {

            return "0";

        }



        // Repeatedly divide 'num' by 2 to find binary representation of num.

        while(num > 0) {

            if(num % 2 == 1) {

                binStr += '1';

            }

            else {

                binStr += '0';

            }

			

            num = num / 2;

        }



        // Reverse 'binStr'.

        binStr = rev(binStr);



        return binStr;

    }

    

	public static String findMissingNumber(ArrayList binaryNums, int n){

        ArrayList present = new ArrayList(n+1);

        

        for(int i=0;i<=n;i++) {

            present.add(i,false);

        }

        

        /*

            Convert all binary strings to integers 

            and mark true at respective index in boolean array 'present'.

        */

        for(int i = 0; i < n; i++) {

            int num = convertToInt(binaryNums.get(i));

            present.set(num, true);

        }



        int missingNum = -1;



        for(int i = 0; i <= n; i++) {

            if(present.get(i) == false) {

                missingNum = i;

                break;

            }

        }



        // Convert missingNum in binary and return it.

        return convertToBin(missingNum);

	}

}

C++ (g++ 5.4)

/*

    Time Complexity : O(N * log(N))

    Space Complexity : O(N)



    Where ‘N’ is the size of the given list binaryNums.

*/



#include 



int convertToInt(string binStr) 

{

    // Length of given binary string.

    int len = binStr.length();



    int num = 0;



    /*

        Traversing from rightmost character (least significant bit) to

        leftmost character (most significant bit).

    */

    for(int i = len - 1; i >= 0; i--) 

    {

        if(binStr[i] == '1') 

        {

            // Note-: (1 << i) = 2 ^ i.

            num += (1 << (len - i - 1));

        }

    }

    return num;

}



string convertToBin(int num) 

{

    string binStr;



    // Corner Case.

    if(num == 0) 

    {

        return "0";

    }



    // Repeatedly divide 'num' by 2 to find binary representation of num.

    while(num > 0) 

    {

        if(num & 1) 

        {

            binStr += '1';

        }

        else 

        {

            binStr += '0';

        }

        num = num / 2;

    }



    // Reverse 'binStr'.

    reverse(binStr.begin(), binStr.end());



    return binStr;

}



string findMissingNumber(vector &binaryNums, int n) 

{

    vector present(n+1);



    /*

        Convert all binary strings to integers 

        and mark true at respective index in boolean array 'present'.

    */

    for(int i = 0; i < n; i++) 

    {

        int num = convertToInt(binaryNums[i]);

        present[num] = true;

    }

    

    int missingNum = -1;



    for(int i = 0; i <= n; i++) 

    {

        if(present[i] == false)

        {

            missingNum = i;

            break;

        }

    }



    // Convert missingNum in binary and return it.

    return convertToBin(missingNum);

}

Python (3.5)

'''

    Time Complexity : O(N * log(N))

    Space Complexity : O(N)



    Where ‘N’ is the size of the given list binaryNums.

'''



def convertToInt(binStr):



    # Length of given binary string.

    l = len(binStr)



    num = 0



    '''

        Traversing from rightmost character (least significant bit) to

        leftmost character (most significant bit).

    '''

    for i in range(l - 1, -1, -1):

        if(binStr[i] == '1'):

            # Note-: (1 << i) = 2 ^ i.

            num += (1 << (l - i - 1))



    return num



def convertToBin(num):

    binStr = ""



    if(num == 0):

        return "0"



    # Repeatedly divide 'num' by 2 to find binary representation of num.

    while(num > 0):

        if(num & 1):

            binStr += '1'

        else:

            binStr += '0'



        num = num // 2



    # Reverse 'binStr'.

    binStr = "".join(reversed(binStr))



    return binStr



def findMissingNumber(binaryNums, n):

    present = [False for i in range(n + 1)]



    '''

        Convert all binary strings to integers 

        and mark true at respective index in boolean array 'present'.

    '''

    for i in range(n):

        num = convertToInt(binaryNums[i])

        present[num] = True



    missingNum = -1



    for i in range(n+1):

        if(present[i] == False):

            missingNum = i

            break



    # Convert missingNum in binary and return it.

    return convertToBin(missingNum)

Accepted Answer

Convert to integers (Xor Property)

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

Space Complexity: O(1)Explanation:

O(1).

We are using constant extra space here.

Time Complexity: O(nlogn)Explanation:

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. Finding xor of all the numbers from 0 to N also takes O(N) times. Thus overall complexity will be O(N * log(N)) + O(N) = O(N * log(N))

C++ (g++ 5.4)

/*

    Time Complexity : O(N * log(N))

    Space Complexity : O(N)



    Where ‘N’ is the size of the given list binaryNums.

*/



#include 



int convertToInt(string binStr) 

{

    // Length of given binary string.

    int len = binStr.length();



    int num = 0;



    /*

        Traversing from rightmost character (least significant bit) to

        leftmost character (most significant bit).

    */

    for(int i = len - 1; i >= 0; i--) 

    {

        if(binStr[i] == '1') 

        {

            // Note-: (1 << i) = 2 ^ i.

            num += (1 << (len - i - 1));

        }

    }

    return num;

}



string convertToBin(int num) 

{

    string binStr;



    // Corner Case.

    if(num == 0) 

    {

        return "0";

    }



    // Repeatedly divide 'num' by 2 to find binary representation of num.

    while(num > 0) 

    {

        if(num & 1) 

        {

            binStr += '1';

        }

        else 

        {

            binStr += '0';

        }

        num = num / 2;

    }



    // Reverse 'binStr'.

    reverse(binStr.begin(), binStr.end());



    return binStr;

}



string findMissingNumber(vector &binaryNums, int n) 

{

    int xorAll = 0, xorNum = 0;



    // Xor of all the integers between 0 and N (inclusive).

    for(int i = 0; i <= n; i++) 

    {

        xorAll = xorAll ^ i;

    }



    // Xor of all the integers represent by string in 'binaryNums'.

    for(int i = 0; i < n; i++) 

    {

        int num = convertToInt(binaryNums[i]);

        xorNum = xorNum ^ num;

    }

    

    int missingNum = xorNum ^ xorAll;



    // Convert missingNum in binary and return it.

    return convertToBin(missingNum);

}

Java (SE 1.8)

/*

    Time Complexity : O(N * log(N))

    Space Complexity : O(N)



    Where N is the size of the given list binaryNums.

*/



import java.util.ArrayList;

    

public class Solution {

    public static String rev(String input) {



        char[] temparray = input.toCharArray();

        int left, right = 0;

        right = temparray.length - 1;

 

        for (left = 0; left < right; left++, right--) {



            // Swap values of left and right.

            char temp = temparray[left];

            temparray[left] = temparray[right];

            temparray[right] = temp;

        }

        String res = "";

        for(char c : temparray) {

            res += c;

        }

        return res;

    }



    public static int convertToInt(String binStr) {



        // Length of given binary string.

        int len = binStr.length();



        int num = 0;



        /*

            Traversing from rightmost character (least significant bit) to

            leftmost character (most significant bit).

        */

        for(int i = len - 1; i >= 0; i--) {

            if(binStr.charAt(i) == '1') {



                // Note-: (1 << i) = 2 ^ i.

                num += (1 << (len - i - 1));

            }

        }

        return num;

    }

    

    public static String convertToBin(int num) {

        String binStr = "";



        // Corner Case.

        if(num == 0) {

            return "0";

        }



        // Repeatedly divide 'num' by 2 to find binary representation of num.

        while(num > 0) {

            if(num % 2 == 1) {

                binStr += '1';

            }

            else {

                binStr += '0';

            }



            num = num / 2;

        }



        // Reverse 'binStr'.

        binStr = rev(binStr);



        return binStr;

    }

    

	public static String findMissingNumber(ArrayList binaryNums, int n){

        int xorAll = 0, xorNum = 0;



        // Xor of all the integers between 0 and N (inclusive).

        for(int i = 0; i <= n; i++) {

            xorAll = xorAll ^ i;

        }



        // Xor of all the integers represent by string in 'binaryNums'.

        for(int i = 0; i < n; i++) {

            int num = convertToInt(binaryNums.get(i));

            xorNum = xorNum ^ num;

        }

        int missingNum = xorNum ^ xorAll;



        // Convert missingNum in binary and return it.

        return convertToBin(missingNum);

	}

}

Python (3.5)

'''

    Time Complexity : O(N * log(N))

    Space Complexity : O(N)



    Where ‘N’ is the size of the given list binaryNums.

'''



def convertToInt(binStr):



    # Length of given binary string.

    l = len(binStr)



    num = 0



    '''

        Traversing from rightmost character (least significant bit) to

        leftmost character (most significant bit).

    '''

    for i in range(l - 1, -1, -1):

        if(binStr[i] == '1'):

            # Note-: (1 << i) = 2 ^ i.

            num += (1 << (l - i - 1))



    return num



def convertToBin(num):

    binStr = ""



    if(num == 0):

        return "0"



    # Repeatedly divide 'num' by 2 to find binary representation of num.

    while(num > 0):

        if(num & 1):

            binStr += '1'

        else:

            binStr += '0'



        num = num // 2



    # Reverse 'binStr'.

    binStr = "".join(reversed(binStr))



    return binStr



def findMissingNumber(binaryNums, n):

    xorAll = xorNum = 0



    # Xor of all the integers between 0 and N (inclusive).

    for i in range(n + 1):

        xorAll = xorAll ^ i



    # Xor of all the integers represent by string in 'binaryNums'.

    for i in range(n):

        num = convertToInt(binaryNums[i])

        xorNum = xorNum ^ num



    missingNum = xorNum ^ xorAll



    # Convert missingNum in binary and return it.

    return convertToBin(missingNum)

Accepted Answer

Without Convert into integers

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’.

Space Complexity: O(1)Explanation:

O(1).

We are using constant extra space here.

Time Complexity: O(nlogn)Explanation:

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

The total number of bits in all the ‘N’ string will be N * log(N). In this approach, we are iterating over every bit. Thus overall time complexity will be O(N * log(N))

Python (3.5)

'''

    Time Complexity : O(N * log(N))

    Space Complexity : O(1)



    Where ‘N’ is the size of the given list binaryNums.

'''



import math



def findMissingNumber(binaryNums, n):



    # Number of bits required to represent 'n'.

    totalBits = int(math.log2(n)) + 1



    missingNum = ""



    for i in range(totalBits):

        '''

            The number of integers between 0 to N (inclusive) that have the ith bit set

            Note -: (1 << i) = 2 ^ i.

        '''

        countReq = (1 << i) * ((n + 1) // (1 << (i + 1))) + \

            max(0, (n + 1) % (1 << (i + 1)) - (1 << i))



        count = 0



        # Count number of integers in given list that have ith bit set.

        for j in range(n):

            l = len(binaryNums[j])

            if(l > i and binaryNums[j][l - i - 1] == '1'):

                count += 1



        if(count != countReq):

            missingNum += '1'

        else:

            missingNum += '0'



    # Remove all leading ‘0’s.

    while(len(missingNum) > 1 and missingNum[-1] == '0'):

        missingNum = missingNum[:-1]



    # Reverse 'missingNum'.

    missingNum = "".join(reversed(missingNum))



    return missingNum

C++ (g++ 5.4)

/*

    Time Complexity : O(N * log(N))

    Space Complexity : O(1)



    where 'N' is the size of the given list 'binaryNums'.

*/



#include 

#include 



string findMissingNumber(vector &binaryNums, int n) 

{



    // Number of bits required to represent 'n'. 

    int totalBits = log2(n) + 1;



    string missingNum;

    for(int i = 0; i < totalBits; i++) 

    {

        /**

            The number of integers between 0 to N (inclusive) that have the ith bit set

            Note -: (1 << i) = 2 ^ i.

        **/

        int countReq = (1 << i) * ((n + 1) / (1 << (i + 1))) + max(0, (n + 1) % (1 << (i + 1)) - (1 << i));

        int count = 0;



        // Count number of integers in given list that have ith bit set.

        for(int j = 0; j < n; j++) 

        {

            int len = binaryNums[j].length();

            if(len > i && binaryNums[j][len-i-1] == '1') 

            {

                count++;

            }

        }

        if(count != countReq) 

        {

            missingNum += '1';

        }

        else 

        {

            missingNum += '0';

        }

    }



    // Remove all leading 0s.

    while(missingNum.length() > 1 && missingNum.back() == '0') 

    {

        missingNum.pop_back();

    }



    // Reverse 'missingNum'.

    reverse(missingNum.begin(), missingNum.end());



    return missingNum;

}

Java (SE 1.8)

/*

    Time Complexity : O(N * log(N))

    Space Complexity : O(1)



    Where N is the size of the given list binaryNums.

*/



import java.util.ArrayList;

import java.lang.*;

 

public class Solution {

    

	// Function to reverse a string.    

    public static String rev(String input){

        char[] temparray = input.toCharArray();

        int left, right = 0;

        right = temparray.length - 1;

 

        for (left = 0; left < right; left++, right--) {



            // Swap values of left and right

            char temp = temparray[left];

            temparray[left] = temparray[right];

            temparray[right] = temp;

        }

		

        String res = "";

        for(char c : temparray) {

            res += c;

        }

        return res;

    }



    // Function to reverse last character of a string.

    public static String removeLastChar(String s) {

        return (s == null || s.length() == 0)? null : (s.substring(0, s.length() - 1));

    }

    

	public static String findMissingNumber(ArrayList binaryNums, int n){



        // Number of bits required to represent 'n'. 

        int totalBits = (int)(Math.log(n) / Math.log(2)) + 1;



        String missingNum = "";

        for(int i = 0; i < totalBits; i++) {



            /*

                The number of integers between 0 to N (inclusive) that have the ith bit set

                Note -: (1 << i) = 2 ^ i.

            */

            int countReq = (1 << i) * ((n + 1) / (1 << (i + 1))) + Math.max(0, (n + 1) % (1 << (i + 1)) - (1 << i));

            int count = 0;



            // Count number of integers in given list that have ith bit set.

            for(int j = 0; j < n; j++) {

                int len = binaryNums.get(j).length();

                if(len > i && binaryNums.get(j).charAt(len - i - 1) == '1') {

                    count++;

                }

            }

            if(count != countReq) {

                missingNum += '1';

            }

            else {

                missingNum += '0';

            }

        }



        // Remove all leading 0s.

        while(missingNum.length() > 1 && missingNum.charAt(missingNum.length() - 1) == '0') {

            missingNum = removeLastChar(missingNum);

        }



        // Reverse missingNum.

        missingNum = rev(missingNum);



        return missingNum;

    }

}

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

Example:

Input format:

Output format :

Note:

Constraints:

Top HexaView Technologies Applications Engineer interview questions & answers

Popular interview questions of Applications Engineer