Количество путей в заданном двоичном дереве с нечетным побитовым И для Q запросов

Опубликовано: 1 Января, 2022

Дано целое число 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
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: Идея состоит в том, чтобы использовать динамическое программирование и предварительное вычисление ответов для всех значений от 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.