Без двух нулей

~2 минуты

Статья написана студентом Хекслета. Мнение автора может не совпадать с позицией редакции

Задание:

Реализуйте и экспортируйте по умолчанию функцию, которая принимает на вход два аргумента - количество нулей и количество единиц, и определяет сколько есть способов размещения этих нулей и единиц так, что бы не было двух нулей идущих подряд.

Например, определим все способы размещения двух нулей и двух единиц. Существует шесть возможных способов размещения:

0011, 0101, 0110, 1001, 1010, 1100. В трех случаях содержится два нуля, идущих подряд: 0011, 1001 и 1100.

Вычитаем их из общего числа и получаем три возможных способа: 0101, 0110 и 1010. Ответ - 3.

Постановка проблемы:

Перед решением задания неприятно удивило, что процент решивших на данный момент всего 55%, для остальных заданий 90-95. Подумалось, что я что то упустил при чтении условия, может есть какой то хитрый подвох, полез читать комментарии, чего только там не было, рекурсия, деревья, комбинаторика, геометрия. В общем, по себе знаю, хочешь сделать надежно, и чтобы и через год понять свое собственное решение - делай как можно проще и прямолинейней - т.е. не плоди лишних сущностей, в данном случае хватит и простого перебора, компьютер быстрый, он справиться.

Решение:

Идея решения проста, по сути нам на вход подается множество двоичных чисел с заданным числом нулей и единиц, переберем их все, от 0 до a + b (с ведущими нулями, в этом нам очень сильно поможет метод String.padStart), где a - количество нулей, b - количество единиц, в процессе перебора будем отбрасывать числа содержащие парные нули (.includes('00')) и числа с количеством нулей и единиц в записи, отличающимся от количества нулей и единиц, заданных параметрами функции. Если запись числа с ведущими нулями не содержит парных нулей, и содержит заданное число нулей и единиц - увеличиваем счетчик на единицу, закончили перебор - вернули значение счетчика. Задание решено.

Примечание:

В переборе всех чисел от 0 до a + b нам не обойтись без метода Number.toString(n) - возвращает число в системе исчисления по основанию n.

Код:

// вернуть количество символов chr в строке str
const numberChar = (str, chr) => {
        let result = 0;
        for (let i = 0; i &lt; str.length; i++) {
            if (chr === str[i]) {
                result++;
            }
        }
        return result;
    }

const withoutTwoZeros = (a, b) => {
    let counter = 0;
    let binaryNum = ''.padStart(a + b, '1');
     for (let index = 0; index &lt;= parseInt(binaryNum, 2); index++) {
        let tmpStr = index.toString(2).padStart(a + b, '0');
        if (!tmpStr.includes('00')) {
            if ((numberChar(tmpStr, '0') === a) && (numberChar(tmpStr, '1') === b)) {
                counter++;
            }
        }
    }
    return counter;
}