Dadas dos listas enlazadas (se pueden ordenar o no) de tamaño n1 y n2 de elementos distintos. Dado un valor X. El problema es contar todos los pares de ambas listas cuyo producto sea igual al valor dado x.
Nota: El par debe tener un elemento de cada lista enlazada.
Ejemplos :
Input : list1 = 3->1->5->7 list2 = 8->2->5->3 X = 10 Output : 1 The pair is: (5, 2) Input : list1 = 4->3->5->7->11->2->1 list2 = 2->3->4->5->6->8-12 X = 9 Output : 1 The pair is: (3, 3)
Un enfoque simple es usar dos elementos de selección de bucles de ambas listas vinculadas y verificar si el producto del par es igual al valor X dado o no. Cuente todos esos pares e imprima el resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to count all pairs from both the // linked lists whose product is equal to // a given value #include <iostream> using namespace std; /* A Linked list node */ struct Node { int data; struct Node* next; }; // function to insert a node at the // beginning of the linked list void push(struct Node** head_ref, int new_data) { /* allocate node */ struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); /* put in the data */ new_node->data = new_data; /* link the old list to the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } // Function to count all pairs from both the linked lists // whose product is equal to a given value int countPairs(struct Node* head1, struct Node* head2, int x) { int count = 0; struct Node *p1, *p2; // Traverse the 1st linked list for (p1 = head1; p1 != NULL; p1 = p1->next) { // for each node of 1st list // Traverse the 2nd list for (p2 = head2; p2 != NULL; p2 = p2->next) { // if sum of pair is equal to 'x' // increment count if ((p1->data * p2->data) == x) count++; } } // required count of pairs return count; } // Driver Code int main() { struct Node* head1 = NULL; struct Node* head2 = NULL; // create linked list1 3->1->5->7 push(&head1, 7); push(&head1, 5); push(&head1, 1); push(&head1, 3); // create linked list2 8->2->5->3 push(&head2, 3); push(&head2, 5); push(&head2, 2); push(&head2, 8); int x = 10; cout << "Count = " << countPairs(head1, head2, x); return 0; }
Java
// Java program to count all pairs from both the // linked lists whose product is equal to // a given value class GFG { /* A Linked list node */ static class Node { int data; Node next; }; // function to insert a node at the // beginning of the linked list static Node push(Node head_ref, int new_data) { /* allocate node */ Node new_node = new Node(); /* put in the data */ new_node.data = new_data; /* link the old list to the new node */ new_node.next = head_ref; /* move the head to point to the new node */ head_ref = new_node; return head_ref; } // Function to count all pairs from both the linked lists // whose product is equal to a given value static int countPairs(Node head1, Node head2, int x) { int count = 0; Node p1, p2; // Traverse the 1st linked list for (p1 = head1; p1 != null; p1 = p1.next) { // for each node of 1st list // Traverse the 2nd list for (p2 = head2; p2 != null; p2 = p2.next) { // if sum of pair is equal to 'x' // increment count if ((p1.data * p2.data) == x) { count++; } } } // required count of pairs return count; } // Driver Code public static void main(String[] args) { Node head1 = null; Node head2 = null; // create linked list1 3.1.5.7 head1 = push(head1, 7); head1 = push(head1, 5); head1 = push(head1, 1); head1 = push(head1, 3); // create linked list2 8.2.5.3 head2 = push(head2, 3); head2 = push(head2, 5); head2 = push(head2, 2); head2 = push(head2, 8); int x = 10; System.out.print("Count = " + countPairs(head1, head2, x)); } } // This code is contributed by Rajput-Ji
Python3
# Python3 program to count all pairs from both the # linked lists whose product is equal to # a given value ''' A Linked list node ''' class Node: def __init__(self, data): self.data = data self.next = None # function to insert a node at the # beginning of the linked list def push(head_ref, new_data): ''' allocate node ''' new_node = Node(new_data) ''' put in the data ''' new_node.data = new_data; ''' link the old list to the new node ''' new_node.next = (head_ref); ''' move the head to point to the new node ''' (head_ref) = new_node; return head_ref # Function to count all pairs from both the linked lists # whose product is equal to a given value def countPairs(head1, head2, x): count = 0; p1 = head1 # Traverse the 1st linked list while p1 != None: p2 = head2 # for each node of 1st list # Traverse the 2nd list while p2 != None: # if sum of pair is equal to 'x' # increment count if ((p1.data * p2.data) == x): count += 1 p2 = p2.next p1 = p1.next # required count of pairs return count; # Driver Code if __name__=='__main__': head1 = None; head2 = None; # create linked list1 3.1.5.7 head1 = push(head1, 7); head1 = push(head1, 5); head1 = push(head1, 1); head1 = push(head1, 3); # create linked list2 8.2.5.3 head2 = push(head2, 3); head2 = push(head2, 5); head2 = push(head2, 2); head2 = push(head2, 8); x = 10; print("Count = " + str(countPairs(head1, head2, x))) # This code is contributed by rutvik_56
C#
// C# program to count all pairs from both the // linked lists whose product is equal to // a given value using System; class GFG { /* A Linked list node */ class Node { public int data; public Node next; }; // function to insert a node at the // beginning of the linked list static Node push(Node head_ref, int new_data) { /* allocate node */ Node new_node = new Node(); /* put in the data */ new_node.data = new_data; /* link the old list to the new node */ new_node.next = head_ref; /* move the head to point to the new node */ head_ref = new_node; return head_ref; } // Function to count all pairs from both the linked lists // whose product is equal to a given value static int countPairs(Node head1, Node head2, int x) { int count = 0; Node p1, p2; // Traverse the 1st linked list for (p1 = head1; p1 != null; p1 = p1.next) { // for each node of 1st list // Traverse the 2nd list for (p2 = head2; p2 != null; p2 = p2.next) { // if sum of pair is equal to 'x' // increment count if ((p1.data * p2.data) == x) { count++; } } } // required count of pairs return count; } // Driver Code public static void Main(String[] args) { Node head1 = null; Node head2 = null; // create linked list1 3->1->5->7 head1 = push(head1, 7); head1 = push(head1, 5); head1 = push(head1, 1); head1 = push(head1, 3); // create linked list2 8->2->5->3 head2 = push(head2, 3); head2 = push(head2, 5); head2 = push(head2, 2); head2 = push(head2, 8); int x = 10; Console.Write("Count = " + countPairs(head1, head2, x)); } } // This code is contributed by Rajput-Ji
Javascript
<script> // javascript program to count all pairs from both the // linked lists whose product is equal to // a given value /* A Linked list node */ class Node { constructor(val) { this.data = val; this.next = null; } } // function to insert a node at the // beginning of the linked list function push(head_ref , new_data) { /* allocate node */ var new_node = new Node(); /* put in the data */ new_node.data = new_data; /* link the old list to the new node */ new_node.next = head_ref; /* move the head to point to the new node */ head_ref = new_node; return head_ref; } // Function to count all pairs from both the linked lists // whose product is equal to a given value function countPairs(head1, head2 , x) { var count = 0; var p1, p2; // Traverse the 1st linked list for (p1 = head1; p1 != null; p1 = p1.next) { // for each node of 1st list // Traverse the 2nd list for (p2 = head2; p2 != null; p2 = p2.next) { // if sum of pair is equal to 'x' // increment count if ((p1.data * p2.data) == x) { count++; } } } // required count of pairs return count; } // Driver Code var head1 = null; var head2 = null; // create linked list1 3.1.5.7 head1 = push(head1, 7); head1 = push(head1, 5); head1 = push(head1, 1); head1 = push(head1, 3); // create linked list2 8.2.5.3 head2 = push(head2, 3); head2 = push(head2, 5); head2 = push(head2, 2); head2 = push(head2, 8); var x = 10; document.write("Count = " + countPairs(head1, head2, x)); // This code contributed by umadevi9616 </script>
Producción:
Count = 1
Complejidad del tiempo: O(N^2)
Publicación traducida automáticamente
Artículo escrito por VishalBachchas y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA