# 1. Tóm tắt đề bài

Bạn được cho một tập $n$ xâu nhị phân độ dài $n$ dưới dạng ```string```.

Bạn cần tìm và in ra một xâu nhị phân độ dài $n$ bất kì **không xuất hiện** trong tập được cho.

##### Giới hạn

- $1 \le n \le 16$.

# 2. Lời giải

Đây là một bài gồm khá nhiều cách giải.

Ta có thể thấy, $1 \le n \le 16$. Vậy nên, với mỗi xâu nhị phân, ta có thể đưa nó về một số nguyên trong hệ cơ số $10$. Lúc này, ta duyệt toàn bộ các số nguyên trong khoảng $[0,2^n-1]$, nếu số đó không xuất hiện trong dãy mới thì ta có kết quả chính là số này dưới dạng nhị phân.

Việc kiểm tra một số có xuất hiện trong dãy hay không, ta có thể dùng một mảng đếm phân phối.

**Note:** Bài toán có thể giải với $n$ lớn hơn, nếu sử dụng ```Trie```.

### Độ phức tạp thuật toán

Thời gian: $O(n)$

### Code

class Solution {
public:
    int value (string &s) {
        int res = 0;
        for (auto u : s) res = res*2 + u - '0';
        return res;
    }
    string bin_val (int n, int sz) {
        string s;
        for (int i=sz-1; i>=0; i--) {
            if (n >> i & 1) s += '1';
            else s+= '0';
        }
        return s;
    }
    static const int N = 2e5+5;
    int mp[N];
    string findDifferentBinaryString(vector<string>& nums) {
        int n = nums.size();
        for (auto s : nums) {
            mp[value(s)]++;
        }
        for (int i=0; i<(1 << n); i++) {
            if (mp[i]) continue;
            return bin_val(i,n);
        }
        return "-1";
    }
};