1980. Find Unique Binary String

Problem Statement

Given an array of strings nums containing n unique binary strings each of length n, return a binary string of length n that does not appear in nums. If there are multiple answers, you may return any of them.

Example 1:

Input: nums = ["01","10"]
Output: "11"
Explanation: "11" does not appear in nums. "00" would also be correct.

Example 2:

Input: nums = ["00","01"]
Output: "11"
Explanation: "11" does not appear in nums. "10" would also be correct.

Example 3:

Input: nums = ["111","011","001"]
Output: "101"
Explanation: "101" does not appear in nums. "000", "010", "100", and "110" would also be correct.

Constraints:

• n == nums.length

• 1 <= n <= 16

• nums[i].length == n

• nums[i] is either '0' or '1'.

• All the strings of nums are unique.

Intuition

Approach 1: Recursion

Approach 2:
Cantors Daigonal Argument

Take one from each index, only when n string of length n
Flip them we gwt a string which never existed

Links

https://leetcode.com/problems/find-unique-binary-string/description/

Video Links

https://www.youtube.com/watch?v=o8KyzI4U9M8&ab_channel=AryanMittal

Approach 1:

C++

class Solution {
public:
    string ans = "";
    unordered_map<string, int> mp;
    bool find_ans(int index, int n){
        if(index == n){
            if(mp.find(ans) == mp.end())
                return true;

            return false;
        }

        if( find_ans(index+1, n) )
            return true;

        ans[index] = '1';
        if( find_ans(index+1, n) )
            return true;

        ans[index] = '0';

        return false;
    }

    string findDifferentBinaryString(vector<string>& nums) {
        for(auto &it: nums)
            mp[it]++;

        int n = nums[0].size();

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

        find_ans(0, n);
        return ans;
    }
};

Approach 2:

C++

class Solution {
public:
    string findDifferentBinaryString(vector<string>& nums) {
        string ans = "";
        
        for(int i =0; i < nums.size(); ++i){
            char curr = nums[i][i];
            ans.push_back(curr == '0'?'1':'0');
        }

        return ans;
    }
};

Approach 3:

C++

Approach 4:

C++

Similar Problems