Задачи
December 25, 2023

Задача. Пропущенная двоичная строка

Дан массив строк nums, содержащий N уникальных двоичных строк длиной N каждая.

Необходимо вернуть двоичную строку длины N, которая нет в nums (если вариантов несколько, верните любой).

Пример:

  • nums = ["01", "10"]
    Output: "11"
    Примечание: "11" пропущен в nums. "00" - также подходит.

Разбор

Одна из простых идей заключается в том, чтобы пройтись по всевозможным двоичным числам заданной длины и проверить есть ли данное число в исходном массиве.

1. Все элементы исходного массива добавляем в хэш-сэт.
2. Так как все элементы массива имеют одинаковую длину, определим длину двоичного числа по 1му элемента: length = nums[0].Length.
3. В этой задаче мы также учитываем ведущие нули для двоичного числа длины length. Например, 0001 - двоичное число длины 4. Поэтому нам фактически нужно пройтись по всем двоичным числам от 0 до максимального двоичного числа длины length. А как определить сколько это?

- Если нам нужно найти все двоичные числа размера 1, то это будут 0 и 1.
- Если нам нужно найти все двоичные числа размера 2, 
то это будут 00, 01, 10, 11.
- Для размера N, количество чисел будет равно 2^N.

4. Теперь мы можем запустить цикл от 0 до 2^length, в цикле каждое число преобразуем в двоичное с ведущими нулями и проверяем есть ли оно в хэш-сете.
5. Возвращаем первый элемент, которого нет в хэш-сете (в исходном массиве).

Реализация

static string FindMissedBinaryString(string[] nums) 
{
    var set = new HashSet<string>(nums);
    var len = nums[0].Length;
    int digitNum = (int)Math.Pow(2, len);

    for (int i = 0; i < digitNum; i++)
    {
        string binary = ConvertNumToBinaryString(i, len);
        if (!set.Contains(binary)) 
        {
            return binary;
        }
    }

    return "";
}

https://gist.github.com/unilecs/26abc5bc60104341e2e4e48defeb898f

Play-test

https://dotnetfiddle.net/OORamt