Unique identifier · Coding Gym

Solutions

A brute force solution involves building the binary string one character at a time, starting from an empty string. At each step, it tries adding a 0 or a 1 and continues until the string reaches length n. When a full-length string is formed, it checks if it’s already in the given list. If it’s not, the function prints it and stops. This approach guarantees that the first missing string found is among the smallest in lexicographical order.

Here is a recursive implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


bool generateId(const string& current, size_t n, const unordered_set<string>& seen)
{
    if (current.size() == n)
    {
        if (!seen.count(current)) // `.cointains(current)` in C++20
        {
            cout << current;
            return true;
        }
        return false;
    }

    return generateId(current + '0', n, seen) || generateId(current + '1', n, seen);
}

int main()
{
    size_t n;
    cin >> n;
    unordered_set<string> seen(istream_iterator<string>(cin), {});
    generateId("", n, seen);
}

In the worst case, the time complexity is \(O(N^2)\), since hashing a string of length \(N\) takes \(O(N)\) and \(N\) strings may need to be checked. The space complexity is \(O(N^2)\) for storing \(N\) strings of length \(N\), plus \(O(N^2)\) for the recursion stack (as we store a string up to length \(N\) at each level).

A similar approach is iterative, for example using a stack:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


size_t n; cin >> n;
unordered_set seen(istream_iterator<string>(cin), {});
stack<string> st;
st.emplace(1, '0');
st.emplace(1, '1');
while (!st.empty())
{
    const auto top = st.top();
    st.pop();
    if (top.size() == n)
    {
        if (!seen.count(top))
        {
            cout << top;
            return 0;
        }
        continue;      
    }
    st.push(top + "0");
    st.push(top + "1");
}

A linear solution

An efficient solution relies on a simple observation: since we have \(N\) binary strings of length \(N\), we can think of them as forming an \(N \cdot N\) grid, one string per row. The diagonal of this grid, made by taking the i-th character from the i-th row, forms a new string of length \(N\). If we flip each bit of this diagonal, the resulting string is guaranteed to differ from every original string in at least one position (specifically, at index i for the i-th string), so it cannot be part of the input list.

For example, suppose we’re given the following 5 binary strings:

If we read the diagonal (the 0th character of the 0th string, the 1st of the 1st, and so on) we get:

1

11011

Flipping each bit of this diagonal string gives:

1

00100

This new string is guaranteed not to appear in the input, because it differs from the i-th string at position i.

This solution is linear in time and constant in space.

This applies Cantor’s diagonal argument, a classical idea from set theory. Originally, Cantor used it to show that some infinite sets, like the real numbers, are uncountable (they can’t be matched one-to-one with the natural numbers). This concept introduced the notion of different sizes of infinity and laid the foundation for cardinality theory. In our setting, we use the same diagonal trick.

Here is the code:

1
2
3
4
5
6
7
8


int n; cin >> n;
string line, ans;
for (auto i=0; i<n; ++i)
{
    cin >> line;
    ans += line[i] == '0' ? '1' : '0';
}
cout << ans;

And this, with ranges:

1
2
3
4


int n; cin >> n;
std::cout << views::istream<string>(cin) | views::enumerate | views::transform([](const auto& p){
    return get<1>(p)[get<0>(p)] == '0' ? '1' : '0';
}) | ranges::to<string>();

Playing with small values of `N`

A useful variation of the problem arises when working with values of \(N\) that can fit into standard integer types (like 32 or 64 bits). Since we’re given \(N\) binary strings of length \(N\), and there are \(N+1\) possible integers in the range \([0, N]\), at least one of them is guaranteed to be missing from the input.

The approach is to convert each binary string into its decimal representation and store these values in a set. Then, by scanning from 0 to N, we can efficiently find the first number that isn’t in the set. This missing number corresponds to a valid binary string that does not appear in the input.

Here is a code example in Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


def genDifferentString(self, nums: List[str]) -> str:
    integers = set()
    for num in nums:
        integers.add(int(num, 2))

    n = len(nums)
    for num in range(n + 1):
        if num not in integers:
            ans = bin(num)[2:]
            return "0" * (n - len(ans)) + ans
        
    return ""

Solutions

A linear solution

Playing with small values of N

Playing with small values of `N`