Dado un número entero Q que representa el número de consultas y una array donde cada consulta tiene un número entero N . Nuestra tarea es iterar a través de cada consulta y encontrar el número de rutas tal que el AND bit a bit de todos los Nodes en esa ruta sea impar.
Un árbol binario se construye con N vértices numerados del 1 al N. Para cada i, de 2 a N, hay una arista entre el vértice i y el vértice i/2 (redondeado) .
Ejemplos:
Input: Q = 2, [5, 2]
Output: 1 0
Explanation:
For first query the binary tree will be
1
/ \
2 3
/ \
4 5
The path which satisfies
the condition is 1 -> 3.
Hence only 1 path.
For the second query,
the binary tree will be
1
/
2
There no such path that
satisfies the condition.
Input: Q = 3, [3, 7, 13]
Output: 1 3 4
Enfoque: La idea es usar Programación Dinámica y precálculo de respuestas para todos los valores desde 1 hasta el valor máximo de N en la consulta.
- En primer lugar, observe que si un AND bit a bit de una ruta es impar, entonces ninguno de los elementos de esa ruta puede ser par . Por lo tanto, la ruta requerida debe tener elementos impares.
- Sabemos que para un i -ésimo Node (excepto el Node 1), el Node principal será i/2 (redondeado). Mantenga una array dp para almacenar la respuesta para el i -ésimo Node. Se usará otra array para almacenar la cantidad de elementos impares del Node actual hasta que los padres sean impares.
- Al calcular la array dp, la primera condición es si el valor del i -ésimo Node es par, entonces dp[i] = dp[i – 1] porque el i -ésimo Node no contribuirá a la respuesta, por lo que dp[i] será la respuesta a (i-1) th Node. En segundo lugar, si el i -ésimo Node es impar, entonces dp[i] = dp[i-1] + nC2 -(n-1)C2. En la simplificación dp[i] = dp[i-1] + (número de elementos impares hasta ahora) – 1.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to count
// paths in Binary Tree
// with odd bitwise AND
#include <bits/stdc++.h>
using namespace std;
// Function to count number of paths
// in binary tree such that bitwise
// AND of all nodes is Odd
void compute(vector<int> query)
{
// vector v for storing
// the count of odd numbers
// vector dp to store the
// count of bitwise odd paths
// till that vertex
vector<int> v(100001), dp(100001);
v[1] = 1, v[2] = 0;
dp[1] = 0, dp[2] = 0;
// Precomputing for each value
for (int i = 3; i < 100001; i++) {
// check for odd value
if (i % 2 != 0) {
if ((i / 2) % 2 == 0) {
v[i] = 1;
dp[i] = dp[i - 1];
}
else {
// Number of odd elements will
// be +1 till the parent node
v[i] = v[i / 2] + 1;
dp[i] = dp[i - 1] + v[i] - 1;
}
}
// For even case
else {
// Since node is even
// Number of odd elements
// will be 0
v[i] = 0;
// Even value node will
// not contribute in answer
// hence dp[i] = previous answer
dp[i] = dp[i - 1];
}
}
// Printing the answer
// for each query
for (auto x : query)
cout << dp[x] << endl;
}
// Driver code
int main()
{
// vector to store queries
vector<int> query = { 5, 2 };
compute(query);
return 0;
}
Java
// Java implementation to count
// paths in Binary Tree
// with odd bitwise AND
class GFG{
// Function to count number of paths
// in binary tree such that bitwise
// AND of all nodes is Odd
static void compute(int[] query)
{
// v for storing the count
// of odd numbers
// dp to store the count of
// bitwise odd paths
// till that vertex
int []v = new int[100001];
int []dp = new int[100001];
v[1] = 1; v[2] = 0;
dp[1] = 0; dp[2] = 0;
// Precomputing for each value
for(int i = 3; i < 100001; i++)
{
// Check for odd value
if (i % 2 != 0)
{
if ((i / 2) % 2 == 0)
{
v[i] = 1;
dp[i] = dp[i - 1];
}
else
{
// Number of odd elements will
// be +1 till the parent node
v[i] = v[i / 2] + 1;
dp[i] = dp[i - 1] + v[i] - 1;
}
}
// For even case
else
{
// Since node is even
// Number of odd elements
// will be 0
v[i] = 0;
// Even value node will
// not contribute in answer
// hence dp[i] = previous answer
dp[i] = dp[i - 1];
}
}
// Printing the answer
// for each query
for(int x : query)
System.out.print(dp[x] + "\n");
}
// Driver code
public static void main(String[] args)
{
// To store queries
int []query = { 5, 2 };
compute(query);
}
}
// This code is contributed by Princi Singh
Python3
# Python3 implementation to count # paths in Binary Tree with odd # bitwise AND # Function to count number of paths # in binary tree such that bitwise # AND of all nodes is Odd def compute(query): # vector v for storing # the count of odd numbers # vector dp to store the # count of bitwise odd paths # till that vertex v = [None] * 100001 dp = [None] * 100001 v[1] = 1 v[2] = 0 dp[1] = 0 dp[2] = 0 # Precomputing for each value for i in range(3, 100001): # Check for odd value if (i % 2 != 0): if ((i // 2) % 2 == 0): v[i] = 1 dp[i] = dp[i - 1] else: # Number of odd elements will # be +1 till the parent node v[i] = v[i // 2] + 1 dp[i] = dp[i - 1] + v[i] - 1 # For even case else: # Since node is even # Number of odd elements # will be 0 v[i] = 0 # Even value node will # not contribute in answer # hence dp[i] = previous answer dp[i] = dp[i - 1] # Printing the answer # for each query for x in query: print(dp[x]) # Driver code # Vector to store queries query = [ 5, 2 ] compute(query) # This code is contributed by sanjoy_62
C#
// C# implementation to count
// paths in Binary Tree
// with odd bitwise AND
using System;
class GFG{
// Function to count number of paths
// in binary tree such that bitwise
// AND of all nodes is Odd
static void compute(int[] query)
{
// v for storing the count
// of odd numbers
// dp to store the count of
// bitwise odd paths
// till that vertex
int []v = new int[100001];
int []dp = new int[100001];
v[1] = 1; v[2] = 0;
dp[1] = 0; dp[2] = 0;
// Precomputing for each value
for(int i = 3; i < 100001; i++)
{
// Check for odd value
if (i % 2 != 0)
{
if ((i / 2) % 2 == 0)
{
v[i] = 1;
dp[i] = dp[i - 1];
}
else
{
// Number of odd elements will
// be +1 till the parent node
v[i] = v[i / 2] + 1;
dp[i] = dp[i - 1] + v[i] - 1;
}
}
// For even case
else
{
// Since node is even
// Number of odd elements
// will be 0
v[i] = 0;
// Even value node will
// not contribute in answer
// hence dp[i] = previous answer
dp[i] = dp[i - 1];
}
}
// Printing the answer
// for each query
foreach(int x in query)
Console.Write(dp[x] + "\n");
}
// Driver code
public static void Main(String[] args)
{
// To store queries
int []query = { 5, 2 };
compute(query);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript implementation to count
// paths in Binary Tree
// with odd bitwise AND
// Function to count number of paths
// in binary tree such that bitwise
// AND of all nodes is Odd
function compute(query)
{
// vector v for storing
// the count of odd numbers
// vector dp to store the
// count of bitwise odd paths
// till that vertex
var v = Array(100001).fill(0);
var dp = Array(100001).fill(0);
v[1] = 1, v[2] = 0;
dp[1] = 0, dp[2] = 0;
// Precomputing for each value
for (var i = 3; i < 100001; i++) {
// check for odd value
if (i % 2 != 0) {
if (parseInt(i / 2) % 2 == 0) {
v[i] = 1;
dp[i] = dp[i - 1];
}
else {
// Number of odd elements will
// be +1 till the parent node
v[i] = v[parseInt(i / 2)] + 1;
dp[i] = dp[i - 1] + v[i] - 1;
}
}
// For even case
else {
// Since node is even
// Number of odd elements
// will be 0
v[i] = 0;
// Even value node will
// not contribute in answer
// hence dp[i] = previous answer
dp[i] = dp[i - 1];
}
}
// Printing the answer
// for each query
query.forEach(x => {
document.write( dp[x] + "<br>");
});
}
// Driver code
// vector to store queries
var query = [5, 2];
compute(query);
</script>
Producción:
1 0
Complejidad de tiempo: O( Nmax + Q*(1) ) , donde Nmax es el valor máximo de N. Q*(1) ya que estamos precalculando cada consulta.
Espacio Auxiliar : O(Nmax)
Publicación traducida automáticamente
Artículo escrito por abhishek_padghan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA