Cuente un par de Nodes con mayor Bitwise AND que Bitwise XOR en la lista vinculada dada

Dada una lista enlazada individualmente , la tarea es Contar los pares de Nodes con mayor Bitwise AND que Bitwise XOR .

Ejemplos:

Entrada: lista: 1->4->2->6->3
Salida: 2
Explicación: 1er par de Nodes de lista: (4, 6 ), AND bit a bit = 4, XOR bit a bit = 2
2do par de Nodes de lista: (2, 3), AND bit a bit = 2, XOR bit a bit = 1

Entrada: lista: 17->34->62->46->30->51
Salida: 7
Explicación: Los pares de Nodes de lista válidos son (17, 30), (34, 62), (34, 46), (34 , 51), (62, 46), (62, 51), (46, 51).

 

Enfoque ingenuo: el enfoque ingenuo consiste en iterar la lista enlazada y, para cada Node, encontrar todos los demás Nodes posibles que formen un par de modo que AND bit a bit sea mayor que XOR bit a bit.

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

Enfoque eficiente: el problema se puede resolver de manera eficiente utilizando la siguiente observación:

Si el bit del primer conjunto (bit más significativo) de dos números está en la misma posición, entonces el AND bit a bit o ese número siempre es mayor que el XOR porque el XOR de dos 1 es 0 y el AND de dos 1 es 1.
Para cualquier otro caso , XOR será siempre mayor que AND

Siga los pasos a continuación para resolver el problema:

  • Recorra la lista vinculada y almacene la posición de MSB para cada valor de Node en una array.
  • Inicializa una variable ans para almacenar el total de pares posibles.
  • Cree un mapa hash para almacenar el recuento de Nodes que tienen el mismo valor de MSB (bit más significativo).
  • Atraviese la array que contiene la posición de MSB y en cada iteración:
    • Obtenga el recuento de Nodes que tienen la misma posición de MSB.
    • Agregue el recuento de posibles pares de estos Nodes a ans .
  • Devuelve la variable de respuesta.

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

C++

// C++ program for above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Structure of node of singly linked list
struct Node {
    int data;
    Node* next;
    Node(int x)
    {
        data = x;
        next = NULL;
    }
};
 
// Inserting new node
// at the  beginning of the linked list
void push(struct Node** head_ref,
          int new_data)
{
    // Create a new node with the given data.
    struct Node* new_node
        = new Node(new_data);
 
    // Make the new node point to the head.
    new_node->next = (*head_ref);
 
    // Make the new node as the head node.
    (*head_ref) = new_node;
}
 
// Function to find the
// count of all possible pairs
int PerfectPair(Node* head, int K)
{
    int ans = 0, size = 0;
    unordered_map<int, int> mp;
    vector<int> firstSetBit;
 
    // Iterate Linked List and store the
    // firstSetBit position
    // for each Node Data
    while (head != NULL) {
        firstSetBit.push_back(
            log2(head->data));
        size++;
        head = head->next;
    }
 
    // Check all previous node
    // which can make
    // pair with current node
    for (int i = 0; i < size; i++) {
        ans += mp[firstSetBit[i]];
        mp[firstSetBit[i]]++;
    }
    return ans;
}
 
// Driver code
int main()
{
    int K = 4;
 
    // Create an empty singly linked list
    struct Node* head = NULL;
 
    // Insert values in Linked List
    push(&head, 51);
    push(&head, 30);
    push(&head, 46);
    push(&head, 62);
    push(&head, 34);
    push(&head, 17);
 
    // Call PerfectPair function
    cout << PerfectPair(head, K);
    return 0;
}

Java

// Java program for above approach
 
import java.util.ArrayList;
import java.util.HashMap;
 
public class GFG {
 
    // Structure of node of singly linked list
    static class Node {
        int data;
        Node next;
        Node(int x) { data = x; }
    };
 
    // Inserting new node
    // at the beginning of the linked list
    static void push(int new_data)
    {
        // Create a new node with the given data.
        Node new_node = new Node(new_data);
 
        // Make the new node point to the head.
        if (head == null) {
            head = new_node;
            return;
        }
 
        new_node.next = head;
 
        // Make the new node as the head node.
        head = new_node;
    }
    static Node head;
 
    // Function to find the
    // count of all possible pairs
    static int PerfectPair(int K)
    {
        int ans = 0, size = 0;
        HashMap<Integer, Integer> mp
            = new HashMap<Integer, Integer>();
        ArrayList<Integer> firstSetBit
            = new ArrayList<Integer>();
 
        // Iterate Linked List and store the
        // firstSetBit position
        // for each Node Data
        while (head != null) {
            firstSetBit.add(log2(head.data));
            size++;
            head = head.next;
        }
 
        // Check all previous node
        // which can make
        // pair with current node
        for (int i = 0; i < size; i++) {
            int val
                = mp.getOrDefault(firstSetBit.get(i), 0);
            ans += val;
            mp.put(firstSetBit.get(i), val + 1);
        }
        return ans;
    }
 
    // Function to calculate the
    // log base 2 of an integer
    public static int log2(int N)
    {
        // calculate log2 N indirectly
        // using log() method
        int result = (int)(Math.log(N) / Math.log(2));
 
        return result;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int K = 4;
 
        // Create an empty singly linked list
        head = null;
 
        // Insert values in Linked List
        push(51);
        push(30);
        push(46);
        push(62);
        push(34);
        push(17);
 
        // Call PerfectPair function
        System.out.println(PerfectPair(K));
    }
}
 
// This code is contributed by jainlovely450

Python3

# Python program for above approach
import math
 
class GFG:
   
    # Structure of node of singly linked list
    class Node:
        data = 0
        next = None
 
        def __init__(self, x):
            self.data = x
             
    # Inserting new node
    # at the beginning of the linked list
    @staticmethod
    def push(new_data):
       
        # Create a new node with the given data.
        new_node = GFG.Node(new_data)
         
        # Make the new node point to the head.
        if (GFG.head == None):
            GFG.head = new_node
            return
        new_node.next = GFG.head
         
        # Make the new node as the head node.
        GFG.head = new_node
    head = None
     
    # Function to find the
    # count of all possible pairs
    @staticmethod
    def PerfectPair(K):
        ans = 0
        size = 0
        mp = dict()
        firstSetBit = []
         
        # Iterate Linked List and store the
        # firstSetBit position
        # for each Node Data
        while (GFG.head != None):
            firstSetBit.append(GFG.log2(GFG.head.data))
            size += 1
            GFG.head = GFG.head.next
             
        # Check all previous node
        # which can make
        # pair with current node
        i = 0
        while (i < size):
            try:
                val = mp[firstSetBit[i]]
            except:
                val = 0
            ans += val
            mp[firstSetBit[i]] = val + 1
            i += 1
        return ans
       
    # Function to calculate the
    # log base 2 of an integer
    @staticmethod
    def log2(N):
       
        # calculate log2 N indirectly
        # using log() method
        result = int((math.log(N) / math.log(2)))
        return result
       
    # Driver code
    @staticmethod
    def main(args):
        K = 4
         
        # Create an empty singly linked list
        GFG.head = None
         
        # Insert values in Linked List
        GFG.push(51)
        GFG.push(30)
        GFG.push(46)
        GFG.push(62)
        GFG.push(34)
        GFG.push(17)
 
        # Call PerfectPair function
        print(GFG.PerfectPair(K))
 
if __name__ == "__main__":
    GFG.main([])
     
'''This Code is written by Rajat Kumar'''

C#

// C# program for above approach
 
using System;
using System.Collections.Generic;
using System.Collections;
static class GFG
{
 
    public class Node
    {
        public int data;
        public  Node next;
        public Node(int x) { data = x; }
    };
    // Structure of node of singly linked list
 
 
    // Inserting new node
    // at the beginning of the linked list
    static void push(int new_data)
    {
        // Create a new node with the given data.
        Node new_node = new Node(new_data);
 
        // Make the new node point to the head.
        if (head == null)
        {
            head = new_node;
            return;
        }
 
        new_node.next = head;
 
        // Make the new node as the head node.
        head = new_node;
    }
    static Node head;
 
    // Function to find the
    // count of all possible pairs
    static int PerfectPair(int K)
    {
        int ans = 0, size = 0;
        Dictionary<int, int> mp = new Dictionary<int, int>();
        ArrayList firstSetBit = new ArrayList();
 
        // Iterate Linked List and store the
        // firstSetBit position
        // for each Node Data
        while (head != null)
        {
            firstSetBit.Add(log2(head.data));
            size++;
            head = head.next;
        }
 
        // Check all previous node
        // which can make
        // pair with current node
        for (int i = 0; i < size; i++)
        {
            int val = mp.GetValueOrDefault((int)firstSetBit[i], 0);
            ans += val;
            mp[(int)firstSetBit[i]] = val + 1;
        }
        return ans;
    }
 
    // Function to calculate the
    // log base 2 of an integer
    public static int log2(int N)
    {
        // calculate log2 N indirectly
        // using log() method
        int result = (int)(Math.Log(N) / Math.Log(2));
 
        return result;
    }
 
    // Driver code
    public static void Main()
    {
        int K = 4;
 
        // Create an empty singly linked list
        head = null;
 
        // Insert values in Linked List
        push(51);
        push(30);
        push(46);
        push(62);
        push(34);
        push(17);
 
        // Call PerfectPair function
        Console.Write(PerfectPair(K));
    }
}
 
// This code is contributed by Saurabh Jaiswal
Producción

7

Complejidad de tiempo: O(N * log N)
Espacio auxiliar: O(N)

Publicación traducida automáticamente

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