Найти любую перестановку двоичной строки заданного размера, отсутствующую в массиве

Учитывая массив arr[] из N различных двоичных строк, каждая из которых имеет N символов, задача состоит в том, чтобы найти любую двоичную строку, содержащую N символов, такую, что она не встречается в данном массиве arr[] .

Пример:

Input: arr[] = {“10”, “01”}
Output: 00
Explanation: String “00” does not appear in array arr[]. Another valid string can be “11” which does not occur in the array arr[] as well.

Input: arr[] {“111”, “011”, “001”}
Output: 101
Explanation: String “101” does not appear in array arr[]. Another valid strings are “000”, “010”, “100”, and “110”.

Наивный подход: Данную проблему можно решить, сгенерировав все двоичные строки, имеющие N бит, и вернув 1 ^-ю строку так, чтобы она не встречалась в данном массиве arr[] .

Временная сложность: O(2 ^N * N ² )
Вспомогательное пространство: O(N)

Эффективный подход: Данную проблему можно оптимизировать, используя метод, аналогичный диагональному аргументу Кантора. Можно заметить, что результирующая строка должна иметь хотя бы один бит, отличный от всех строк в arr[] . Следовательно, результирующая двоичная строка может быть построена путем принятия дополнения 1 ^-го элемента 1 ^-й строки в качестве 1 ^-го элемента, дополнения 2- ^го элемента 2- ^й строки в качестве 2- ^го элемента и так далее. . Ниже приведены шаги, которые необходимо выполнить:

• Создайте строку ans , в которой хранится результирующая строка. Изначально он пустой.
• Перебрать заданные строки в диагональном порядке, т. е. 1 ^-й элемент 1 ^-й строки, 2- ^й элемент 2- ^й строки и т. д., и добавить дополнение значения по текущему индексу в строку ans .
• Строка, сохраненная в ans после итерации по всему массиву arr[] , является одной из требуемых допустимых строк.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(1)