Consultas para encontrar el valor máximo de Xor entre X y los Nodes de un nivel dado de un árbol binario perfecto

Posted on by Rudeus Greyrat

Dado un árbol binario perfecto de N Nodes, con Nodes que tienen valores de 1 a N como se muestra en la imagen a continuación y Q consultas donde cada consulta consta de dos números enteros L y X . La tarea es encontrar el valor máximo posible de X XOR Y donde Y puede ser cualquier Node en el nivel L . 
 

Ejemplos: 

Entrada: Q[] = {{2, 5}, {3, 15}} 
Salida: 
7 
11 
1ra Consulta: El nivel 2 tiene los números 2 y 3. 
Por lo tanto, 2^5 = 7 y 3^5 = 6. 
Por lo tanto, la respuesta es 7. 
2da Consulta: El nivel 3 tiene los números 4, 5, 6 y 7 
y 4^15 = 11 es el máximo posible.

Entrada: Q[] = {{ 1, 15 }, { 5, 23 }} 
Salida: 
14 
15 
 

Enfoque: Los números en el nivel L contienen L bits, por ejemplo, en el nivel 2 los números son 2 y 3 que pueden representarse usando 2 bits en binario. Del mismo modo, en el nivel 3 los números son 4, 5, 6 y 7 se pueden representar con 3 bits. 
Entonces tenemos que encontrar un número de bit L que dé el máximo xor con X . Almacene los bits de X en una array a[] . Ahora, complete una array b[] de tamaño L con elementos opuestos a los de a[] , es decir, si a[i] es igual a 0, entonces ponga b[i] igual a 1 y viceversa. 
Nótese que el índice L-1 deb[] siempre debe ser 1. Si el tamaño de a[] es menor que b[] , complete los índices restantes de b[] con 1. La array b[] se llena de manera opuesta a la de la array a[] para que el El número hecho a partir de los bits de la array b[] da el valor máximo de xor. Por último, calcule el número formado por b[] y devuelva su xor con X como respuesta a la consulta.

A continuación se muestra la implementación del enfoque anterior:  

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define MAXN 60
 
// Function to solve queries of the maximum xor value
// between the nodes in a given level L of a
// perfect binary tree and a given value X
int solveQuery(int L, int X)
{
    // Initialize result
    int res;
 
    // Initialize array to store bits
    int a[MAXN], b[L];
 
    // Initialize a copy of X
    // and size of array
    int ref = X, size_a = 0;
 
    // Storing the bits of X
    // in the array a[]
    while (ref > 0) {
        a[size_a] = ref % 2;
        ref /= 2;
        size_a++;
    }
 
    // Filling the array b[]
    for (int i = 0; i < min(size_a, L); i++) {
        if (a[i] == 1)
            b[i] = 0;
        else
            b[i] = 1;
    }
 
    for (int i = min(size_a, L); i < L; i++)
        b[i] = 1;
 
    b[L - 1] = 1;
 
    // Initializing variable which gives
    // maximum xor
    int temp = 0, p = 1;
 
    for (int i = 0; i < L; i++) {
        temp += b[i] * p;
        p *= 2;
    }
 
    // Getting the maximum xor value
    res = temp ^ X;
 
    // Return the result
    return res;
}
 
// Driver code
int main()
{
    int queries[][2] = { { 2, 5 }, { 3, 15 } };
    int q = sizeof(queries) / sizeof(queries[0]);
 
    // Perform queries
    for (int i = 0; i < q; i++)
        cout << solveQuery(queries[i][0],
                           queries[i][1])
             << endl;
 
    return 0;
}

Java

// Java implementation of the approach
 
class GFG
{
     
    static int MAXN = 60;
     
    // Function to solve queries of the maximum xor value
    // between the nodes in a given level L of a
    // perfect binary tree and a given value X
    static int solveQuery(int L, int X)
    {
        // Initialize result
        int res;
     
        // Initialize array to store bits
        int []a = new int [MAXN];
        int []b = new int[L];
     
        // Initialize a copy of X
        // and size of array
        int refer = X, size_a = 0;
     
        // Storing the bits of X
        // in the array a[]
        while (refer > 0)
        {
            a[size_a] = refer % 2;
            refer /= 2;
            size_a++;
        }
     
        // Filling the array b[]
        for (int i = 0; i < Math.min(size_a, L); i++)
        {
            if (a[i] == 1)
                b[i] = 0;
            else
                b[i] = 1;
        }
     
        for (int i = Math.min(size_a, L); i < L; i++)
            b[i] = 1;
     
        b[L - 1] = 1;
     
        // Initializing variable which gives
        // maximum xor
        int temp = 0, p = 1;
     
        for (int i = 0; i < L; i++)
        {
            temp += b[i] * p;
            p *= 2;
        }
     
        // Getting the maximum xor value
        res = temp ^ X;
     
        // Return the result
        return res;
    }
     
    // Driver code
    static public void main (String args[])
    {
        int [][]queries= { { 2, 5 }, { 3, 15 } };
        int q = queries.length;
     
        // Perform queries
        for (int i = 0; i < q; i++)
            System.out.println( solveQuery(queries[i][0],
                            queries[i][1]) );
         
    }
}
 
// This code is contributed by AnkitRai01

Python3

# Python3 implementation of the approach
 
MAXN = 60
 
# Function to solve queries of the maximum xor value
# between the nodes in a given level L of a
# perfect binary tree and a given value X
def solveQuery(L, X):
     
    # Initialize result
    res = 0
 
    # Initialize array to store bits
    a = [0 for i in range(MAXN)]
    b = [0 for i in range(MAXN)]
 
    # Initialize a copy of X
    # and size of array
    ref = X
    size_a = 0
 
    # Storing the bits of X
    # in the array a[]
    while (ref > 0):
        a[size_a] = ref % 2
        ref //= 2
        size_a+=1
 
    # Filling the array b[]
    for i in range(min(size_a,L)):
        if (a[i] == 1):
            b[i] = 0
        else:
            b[i] = 1
 
 
    for i in range(min(size_a, L),L):
        b[i] = 1
 
    b[L - 1] = 1
 
    # Initializing variable which gives
    # maximum xor
    temp = 0
    p = 1
 
    for i in range(L):
        temp += b[i] * p
        p *= 2
 
    # Getting the maximum xor value
    res = temp ^ X
 
    # Return the result
    return res
 
# Driver code
queries= [ [ 2, 5 ], [ 3, 15 ] ]
 
q = len(queries)
 
# Perform queries
for i in range(q):
    print(solveQuery(queries[i][0],queries[i][1]))
 
# This code is contributed by mohit kumar 29

C#

// C# implementation of the approach
using System;
 
class GFG
{
     
    static int MAXN = 60;
     
    // Function to solve queries of the maximum xor value
    // between the nodes in a given level L of a
    // perfect binary tree and a given value X
    static int solveQuery(int L, int X)
    {
        // Initialize result
        int res;
     
        // Initialize array to store bits
        int []a = new int [MAXN];
        int []b = new int[L];
     
        // Initialize a copy of X
        // and size of array
        int refer = X, size_a = 0;
     
        // Storing the bits of X
        // in the array a[]
        while (refer > 0)
        {
            a[size_a] = refer % 2;
            refer /= 2;
            size_a++;
        }
     
        // Filling the array b[]
        for (int i = 0; i < Math.Min(size_a, L); i++)
        {
            if (a[i] == 1)
                b[i] = 0;
            else
                b[i] = 1;
        }
     
        for (int i = Math.Min(size_a, L); i < L; i++)
            b[i] = 1;
     
        b[L - 1] = 1;
     
        // Initializing variable which gives
        // maximum xor
        int temp = 0, p = 1;
     
        for (int i = 0; i < L; i++)
        {
            temp += b[i] * p;
            p *= 2;
        }
     
        // Getting the maximum xor value
        res = temp ^ X;
     
        // Return the result
        return res;
    }
     
    // Driver code
    static public void Main ()
    {
        int [,]queries= { { 2, 5 }, { 3, 15 } };
        int q = queries.Length;
     
        // Perform queries
        for (int i = 0; i < q; i++)
            Console.WriteLine( solveQuery(queries[i,0],
                            queries[i,1]) );
         
    }
}
 
// This code is contributed by anuj_67..

Javascript

<script>
 
// Javascript implementation of the approach
var MAXN = 60;
 
// Function to solve queries of the maximum
// xor value between the nodes in a given
// level L of a perfect binary tree and a
// given value X
function solveQuery(L, X)
{
     
    // Initialize result
    var res;
 
    // Initialize array to store bits
    var a = Array(MAXN), b = Array(L);
 
    // Initialize a copy of X
    // and size of array
    var ref = X, size_a = 0;
 
    // Storing the bits of X
    // in the array a[]
    while (ref > 0)
    {
        a[size_a] = ref % 2;
        ref = parseInt(ref / 2);
        size_a++;
    }
 
    // Filling the array b[]
    for(var i = 0; i < Math.min(size_a, L); i++)
    {
        if (a[i] == 1)
            b[i] = 0;
        else
            b[i] = 1;
    }
 
    for(var i = Math.min(size_a, L); i < L; i++)
        b[i] = 1;
 
    b[L - 1] = 1;
 
    // Initializing variable which gives
    // maximum xor
    var temp = 0, p = 1;
 
    for(var i = 0; i < L; i++)
    {
        temp += b[i] * p;
        p *= 2;
    }
 
    // Getting the maximum xor value
    res = temp ^ X;
 
    // Return the result
    return res;
}
 
// Driver code
var queries = [ [ 2, 5 ], [ 3, 15 ] ];
var q = queries.length;
 
// Perform queries
for(var i = 0; i < q; i++)
    document.write(solveQuery(queries[i][0],
                              queries[i][1]) + "<br>");
                               
// This code is contributed by rutvik_56
 
</script>
Producción: 

7
11

 

Publicación traducida automáticamente

Artículo escrito por rupesh_rao y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *