Find Unique Binary String

Leetcode Problem:

• Find Unique Binary String

Summary

• Given an array of unique binary strings, return a binary string that does not appear in the array.

Approach

• The solution uses a set data structure to store the binary numbers represented by the input strings
• It then iterates over all possible binary numbers of the same length as the input strings, checks if each number is in the set, and returns the first number that is not in the set.

Complexity

• O(2^n * n) where n is the length of the input strings

Explanation

• The solution first converts each binary string to a decimal number using the `makeNum` function
• It then stores these decimal numbers in a set
• The `makeStr` function is used to convert a decimal number back to a binary string
• The solution then iterates over all possible binary numbers of the same length as the input strings, checks if each number is in the set, and returns the first number that is not in the set
• This approach ensures that the solution finds the first binary string that does not appear in the input array.

Solution Code:

class Solution {
public:
    int makeNum(string s){
        int num = 0;
        for(int i = 0 ; i < s.size(); i++){
            num *= 2;
            num += s[i] - '0';
        }
        return num;
    }
    string makeStr(int num, int length){
        string res = "";
        for(int i = 0 ; i < length; i++){
            res = string(1, '0'+(num %2)) + res;
            num /= 2;
        }
        return res;
    }
    bool set[1<<16];
    string findDifferentBinaryString(vector& nums) {
        int length = nums[0].size();
        for(int i = 0 ; i < nums.size(); i++){
            set[makeNum(nums[i])] = true;
        }
        for(int i = 0 ; i < (1 << 16); i++){
            if(set[i]){
                continue;
            }
            return makeStr(i, length);
        }
        return "";
    }
};