Longitud de ruta más corta entre dos Nodes dados, de modo que los Nodes adyacentes tengan una diferencia de bit 2

Posted on by Rudeus Greyrat

Dado un gráfico no ponderado y no dirigido que consta de N Nodes y dos números enteros a y b . El borde entre dos Nodes cualesquiera existe solo si la diferencia de bits entre ellos es 2 , la tarea es encontrar la longitud del camino más corto entre los Nodes a y b . Si no existe una ruta entre los Nodes ayb , imprima -1 .

Ejemplos:

Entrada: N = 15, a = 15, b = 3
Salida: 1
Explicación: a = 15 = (1111) 2 yb = 3 = (0011) 2 . La diferencia de bits entre 15 y 3 es 2. Por lo tanto, hay un borde directo entre 15 y 3. Por lo tanto, la longitud del camino más corto es 1.

Entrada: N = 15, a = 15, b = 2
Salida: -1
Explicación: a = 15 = (1111) 2 yb= 2 = (0010) 2 . La diferencia de bits entre 15 y 2 es 3. Como la diferencia de bits solo puede ser 2, es imposible llegar a 15
desde 2.

Enfoque ingenuo: el enfoque más simple para resolver este problema es construir primero el gráfico usando las condiciones dadas, luego encontrar el camino más corto entre los Nodes usando a y b usando bfs considerando a como el Node fuente del gráfico.

Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N) 

Enfoque eficiente: el problema se puede resolver observando que la suma de las diferencias de bits entre dos Nodes cualesquiera debe ser un factor 2 y su distancia más corta debe ser la mitad de esa suma. Siga los pasos que se indican a continuación para comprender el enfoque:

  1. El conteo de bits establecidos en Bitwise XOR de a y b da el conteo de diferencia de bits entre los Nodes a y b .
  2. Si el recuento de bits establecidos en Bitwise XOR de a y b es un múltiplo de 2 , entonces a y b están conectados.
  3. Si el recuento de bits establecidos es 2 , eso significa que están a 1 unidad de distancia entre sí. Si el recuento de bits establecidos en xor de a y b es 4 , eso significa que los Nodes a y b están separados por 2 unidades. Por lo tanto, si la diferencia de bits es x , entonces el camino más corto sería x/2 .
  4. Si la diferencia de bits es impar, entonces no están conectados, por lo tanto, imprima -1 .

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

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count set bits
// in a number
int countbitdiff(int xo)
{
 
    // Stores count of
    // set bits in xo
    int count = 0;
 
    // Iterate over each
    // bits of xo
    while (xo) {
 
        // If current bit of xo
        // is 1
        if (xo % 2 == 1) {
 
            //  Update count
            count++;
        }
 
        // Update xo
        xo = xo / 2;
    }
    return count;
}
 
// Function to find length of shortest
// path between the nodes a and b
void shortestPath(int n, int a, int b)
{
 
    // Stores XOR of a and b
    int xorVal = a ^ b;
 
    // Stores the count of
    // set bits in xorVal
    int cnt = countbitdiff(xorVal);
 
    // If cnt is an even number
    if (cnt % 2 == 0)
        cout << cnt / 2 << endl;
    else
        cout << "-1" << endl;
}
 
// Driver Code
int main()
{
    // Given N
    int n = 15;
 
    // Given a and b
    int a = 15, b = 3;
 
    // Function call
    shortestPath(n, a, b);
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
     
// Function to count set bits
// in a number
static int countbitdiff(int xo)
{
     
    // Stores count of
    // set bits in xo
    int count = 0;
 
    // Iterate over each
    // bits of xo
    while (xo != 0)
    {
         
        // If current bit of xo
        // is 1
        if (xo % 2 == 1)
        {
             
            // Update count
            count++;
        }
         
        // Update xo
        xo = xo / 2;
    }
    return count;
}
 
// Function to find length of shortest
// path between the nodes a and b
static void shortestPath(int n, int a, int b)
{
     
    // Stores XOR of a and b
    int xorVal = a ^ b;
 
    // Stores the count of
    // set bits in xorVal
    int cnt = countbitdiff(xorVal);
 
    // If cnt is an even number
    if (cnt % 2 == 0)
        System.out.print(cnt / 2);
    else
        System.out.print("-1");
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given N
    int n = 15;
 
    // Given a and b
    int a = 15, b = 3;
 
    // Function call
    shortestPath(n, a, b);
}   
}
 
// This code is contributed by susmitakundugoaldanga

Python3

# Python3 program for the above approach
 
# Function to count set bits
# in a number
def countbitdiff(xo):
 
    # Stores count of
    # set bits in xo
    count = 0
 
    # Iterate over each
    # bits of xo
    while (xo):
 
        # If current bit of xo
        # is 1
        if (xo % 2 == 1):
            #  Update count
            count+=1
 
 
        # Update xo
        xo = xo // 2
 
    return count
 
 
# Function to find length of shortest
# path between the nodes a and b
def shortestPath(n, a, b):
 
    # Stores XOR of a and b
    xorVal = a ^ b
 
    # Stores the count of
    # set bits in xorVal
    cnt = countbitdiff(xorVal)
 
    # If cnt is an even number
    if (cnt % 2 == 0):
        print(cnt // 2)
    else:
        print("-1")
 
 
# Driver Code
if __name__ == '__main__':
    # Given N
    n = 15
 
    # Given a and b
    a,b = 15,3
 
    # Function call
    shortestPath(n, a, b)
 
# This code is contributed by mohit kumar 29.

C#

// C# program for the above approach
using System;
 
class GFG {
 
// Function to count set bits
// in a number
static int countbitdiff(int xo)
{
     
    // Stores count of
    // set bits in xo
    int count = 0;
 
    // Iterate over each
    // bits of xo
    while (xo != 0)
    {
         
        // If current bit of xo
        // is 1
        if (xo % 2 == 1)
        {
             
            // Update count
            count++;
        }
         
        // Update xo
        xo = xo / 2;
    }
    return count;
}
 
// Function to find length of shortest
// path between the nodes a and b
static void shortestPath(int n, int a, int b)
{
     
    // Stores XOR of a and b
    int xorVal = a ^ b;
 
    // Stores the count of
    // set bits in xorVal
    int cnt = countbitdiff(xorVal);
 
    // If cnt is an even number
    if (cnt % 2 == 0)
        Console.Write(cnt / 2);
    else
        Console.Write("-1");
}
 
  // Driver code
  public static void Main (String[] args)
  {
 
    // Given N
    int n = 15;
 
    // Given a and b
    int a = 15, b = 3;
 
    // Function call
    shortestPath(n, a, b);
  }
}
 
 
// This code is contributed by code_hunt.

Javascript

<script>
// Javascript program for the above approach
 
// Function to count set bits
// in a number
function countbitdiff(xo) {
 
    // Stores count of
    // set bits in xo
    let count = 0;
 
    // Iterate over each
    // bits of xo
    while (xo) {
 
        // If current bit of xo
        // is 1
        if (xo % 2 == 1) {
 
            //  Update count
            count++;
        }
 
        // Update xo
        xo = Math.floor(xo / 2);
    }
    return count;
}
 
// Function to find length of shortest
// path between the nodes a and b
function shortestPath(n, a, b) {
 
    // Stores XOR of a and b
    let xorVal = a ^ b;
 
    // Stores the count of
    // set bits in xorVal
    let cnt = countbitdiff(xorVal);
 
    // If cnt is an even number
    if (cnt % 2 == 0)
        document.write(cnt / 2 + "<br>");
    else
        document.write("-1" + "<br>");
}
 
// Driver Code
 
// Given N
let n = 15;
 
// Given a and b
let a = 15, b = 3;
 
// Function call
shortestPath(n, a, b);
 
// This code is contributed by gfgking.
</script>
Producción:

1

 

Complejidad temporal: O(log 2 (N)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por heimanth 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 *