Find Unique Binary String

This question has to be misclassified.

I sorted nums and iterated through all the elements in nums until I found one that was missing, and returned it.

code

class Solution {
public:
    string findDifferentBinaryString(vector<string>& nums) {
        sort(nums.begin(), nums.end());
        string temp(nums.size(), '0');
        for (int i = 0; i < nums.size(); ++i) {
            if (temp != nums[i]) {
                return temp;
            }
            int index = nums.size()-1;
            while(temp[index] == '1') {
                temp[index--] = '0';
            }
            temp[index] = '1';
        }
        return temp;
    }
};

complexity

• Time: O(n^2)
• Space: O(n)

However, you can just use Cantor's Diagonal Argument.

Just iterate through all n elements, and generate a string of length n, ans, by making the ith bit in ans the opposite of the ith bit in nums[i] for 0 <= i < n. Then, you know that ans is unique, since there is at least 1 bit that is different in ans to every element in nums.

code

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

learnings

• the existence of Cantor's Diagonal Argument

time taken

• 16 minutes and 31.57 seconds
  • slightly embarrassing honestly; I forgot how to do string manipulation...