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 = 1Entrada: 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