Количество путей в заданном двоичном дереве с нечетным побитовым И для Q запросов
Дано целое число Q, представляющее количество запросов, и массив, в котором каждый запрос имеет целое число N. Наша задача - перебрать каждый запрос и найти такое количество путей, чтобы побитовое И всех узлов на этом пути было нечетным.
A binary tree is constructed with N vertices numbered 1 through N. For each i, from 2 to N, there is an edge between vertex i and vertex i / 2 (rounded off).
Примеры:
Ввод: Q = 2, [5, 2] Выход: 1 0 Объяснение: Для первого запроса двоичное дерево будет 1 / 2 3 / 4 5 Путь, который удовлетворяет условие 1 -> 3. Значит только 1 путь. Для второго запроса двоичное дерево будет 1 / 2 Нет такого пути, что удовлетворяет условию. Ввод: Q = 3, [3, 7, 13] Выход: 1 3 4
Подход: Идея состоит в том, чтобы использовать динамическое программирование и предварительное вычисление ответов для всех значений от 1 до максимального значения N в запросе.
- Во-первых, обратите внимание, что если поразрядное И пути нечетное, то ни один элемент этого пути не может быть четным . Следовательно, искомый путь должен иметь нечетные элементы.
- Мы знаем, что для i- го узла (кроме узла 1) родительский узел будет i / 2 (с округлением). Поддержите массив dp для хранения ответа для i- го узла. Другой массив будет использоваться для хранения количества нечетных элементов от текущего узла до нечетных родительских элементов.
- При вычислении массива dp первое условие: если значение i- го узла четное, тогда dp [i] = dp [i - 1], потому что i- й узел не будет вносить вклад в ответ, поэтому dp [i] будет ответ на (i-1) -й узел. Во-вторых, если i- й узел нечетный, то dp [i] = dp [i-1] + nC2 - (n-1) C2. По упрощению dp [i] = dp [i-1] + (количество нечетных элементов до сих пор) - 1.
Ниже представлена реализация описанного выше подхода:
Сложность времени: O (Nmax + Q * (1)) , где Nmax - максимальное значение N. Q * (1), поскольку мы предварительно вычисляем каждый запрос.
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по доступной для студентов цене и будьте готовы к работе в отрасли. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене.
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.