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 cuya suma sea igual al valor x dado .
Nota: El par tiene un elemento de cada lista enlazada.
Ejemplos:
Input : list1 = 3->1->5->7
list2 = 8->2->5->3
x = 10
Output : 2
The pairs are:
(5, 5) and (7, 3)
Input : list1 = 4->3->5->7->11->2->1
list2 = 2->3->4->5->6->8-12
x = 9
Output : 5
Método 1 (enfoque ingenuo): utilizando dos bucles, seleccione elementos de ambas listas vinculadas y verifique si la suma del par es igual a x o no.
Implementación:
C++
// C++ implementation to count pairs from both linked
// lists whose sum is equal to a given value
#include <bits/stdc++.h>
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 sum 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 program to test above
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 implementation to count pairs from both linked
// lists whose sum is equal to a given value
// Note : here we use java.util.LinkedList for
// linked list implementation
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;
class GFG
{
// method to count all pairs from both the linked lists
// whose sum is equal to a given value
static int countPairs(LinkedList<Integer> head1, LinkedList<Integer> head2, int x)
{
int count = 0;
// traverse the 1st linked list
Iterator<Integer> itr1 = head1.iterator();
while(itr1.hasNext())
{
// for each node of 1st list
// traverse the 2nd list
Iterator<Integer> itr2 = head2.iterator();
Integer t = itr1.next();
while(itr2.hasNext())
{
// if sum of pair is equal to 'x'
// increment count
if ((t + itr2.next()) == x)
count++;
}
}
// required count of pairs
return count;
}
// Driver method
public static void main(String[] args)
{
Integer arr1[] = {3, 1, 5, 7};
Integer arr2[] = {8, 2, 5, 3};
// create linked list1 3->1->5->7
LinkedList<Integer> head1 = new LinkedList<>(Arrays.asList(arr1));
// create linked list2 8->2->5->3
LinkedList<Integer> head2 = new LinkedList<>(Arrays.asList(arr2));
int x = 10;
System.out.println("Count = " + countPairs(head1, head2, x));
}
}
Python3
# Python3 implementation to count pairs from both linked
# lists whose sum 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):
new_node=Node(new_data)
#new_node.data = new_data
new_node.next = head_ref
head_ref = new_node
return head_ref
# function to count all pairs from both the linked lists
# whose sum is equal to a given value
def countPairs(head1, head2, x):
count = 0
#struct Node p1, p2
# traverse the 1st linked list
p1 = head1
while(p1 != None):
# for each node of 1st list
# traverse the 2nd list
p2 = head2
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 program to test above
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 = ",countPairs(head1, head2, x))
# This code is contributed by AbhiThakur
C#
// C# implementation to count pairs from both linked
// lists whose sum is equal to a given value
using System;
using System.Collections.Generic;
// Note : here we use using System.Collections.Generic for
// linked list implementation
class GFG
{
// method to count all pairs from both the linked lists
// whose sum is equal to a given value
static int countPairs(List<int> head1, List<int> head2, int x)
{
int count = 0;
// traverse the 1st linked list
foreach(int itr1 in head1)
{
// for each node of 1st list
// traverse the 2nd list
int t = itr1;
foreach(int itr2 in head2)
{
// if sum of pair is equal to 'x'
// increment count
if ((t + itr2) == x)
count++;
}
}
// required count of pairs
return count;
}
// Driver code
public static void Main(String []args)
{
int []arr1 = {3, 1, 5, 7};
int []arr2 = {8, 2, 5, 3};
// create linked list1 3->1->5->7
List<int> head1 = new List<int>(arr1);
// create linked list2 8->2->5->3
List<int> head2 = new List<int>(arr2);
int x = 10;
Console.WriteLine("Count = " + countPairs(head1, head2, x));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// javascript implementation to count pairs from both linked
// lists whose sum is equal to a given value
// Note : here we use java.util.LinkedList for
// linked list implementation
// method to count all pairs from both the linked lists
// whose sum is equal to a given value
function countPairs( head1, head2 , x) {
var count = 0;
// traverse the 1st linked list
for (var itr1 of head1) {
// for each node of 1st list
// traverse the 2nd list
for (var itr2 of head2) {
// if sum of pair is equal to 'x'
// increment count
if ((itr1 + itr2) == x)
count++;
}
}
// required count of pairs
return count;
}
// Driver method
var arr1 = [ 3, 1, 5, 7 ];
var arr2 = [ 8, 2, 5, 3 ];
// create linked list1 3->1->5->7
var head1 = (arr1);
// create linked list2 8->2->5->3
var head2 = arr2;
var x = 10;
document.write("Count = " + countPairs(head1, head2, x));
// This code is contributed by Rajput-Ji
</script>
Producción
Count = 2
Complejidad de tiempo: O(n1*n2)
Espacio auxiliar: O(1)
Método 2 (Clasificación): Ordene la primera lista enlazada en orden ascendente y la segunda lista enlazada en orden descendente utilizando la técnica de clasificación por combinación. Ahora recorra ambas listas de izquierda a derecha de la siguiente manera:
Algoritmo:
countPairs(list1, list2, x)
Initialize count = 0
while list1 != NULL and list2 != NULL
if (list1->data + list2->data) == x
list1 = list1->next
list2 = list2->next
count++
else if (list1->data + list2->data) > x
list2 = list2->next
else
list1 = list1->next
return count
Para simplificar, la implementación que se da a continuación asume que list1 se ordena en orden ascendente y list2 se ordena en orden descendente.
Implementación:
C++
// C++ implementation to count pairs from both linked
// lists whose sum is equal to a given value
#include <bits/stdc++.h>
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 sum is equal to a given value
int countPairs(struct Node* head1, struct Node* head2,
int x)
{
int count = 0;
// sort head1 in ascending order and
// head2 in descending order
// sort (head1), sort (head2)
// For simplicity both lists are considered to be
// sorted in the respective orders
// traverse both the lists from left to right
while (head1 != NULL && head2 != NULL)
{
// if this sum is equal to 'x', then move both
// the lists to next nodes and increment 'count'
if ((head1->data + head2->data) == x)
{
head1 = head1->next;
head2 = head2->next;
count++;
}
// if this sum is greater than x, then
// move head2 to next node
else if ((head1->data + head2->data) > x)
head2 = head2->next;
// else move head1 to next node
else
head1 = head1->next;
}
// required count of pairs
return count;
}
// Driver program to test above
int main()
{
struct Node* head1 = NULL;
struct Node* head2 = NULL;
// create linked list1 1->3->5->7
// assumed to be in ascending order
push(&head1, 7);
push(&head1, 5);
push(&head1, 3);
push(&head1, 1);
// create linked list2 8->5->3->2
// assumed to be in descending order
push(&head2, 2);
push(&head2, 3);
push(&head2, 5);
push(&head2, 8);
int x = 10;
cout << "Count = "
<< countPairs(head1, head2, x);
return 0;
}
Java
// Java implementation to count pairs from both linked
// lists whose sum is equal to a given value
// Note : here we use java.util.LinkedList for
// linked list implementation
import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
class GFG
{
// method to count all pairs from both the linked lists
// whose sum is equal to a given value
static int countPairs(LinkedList<Integer> head1, LinkedList<Integer> head2, int x)
{
int count = 0;
// sort head1 in ascending order and
// head2 in descending order
Collections.sort(head1);
Collections.sort(head2,Collections.reverseOrder());
// traverse both the lists from left to right
Iterator<Integer> itr1 = head1.iterator();
Iterator<Integer> itr2 = head2.iterator();
Integer num1 = itr1.hasNext() ? itr1.next() : null;
Integer num2 = itr2.hasNext() ? itr2.next() : null;
while(num1 != null && num2 != null)
{
// if this sum is equal to 'x', then move both
// the lists to next nodes and increment 'count'
if ((num1 + num2) == x)
{
num1 = itr1.hasNext() ? itr1.next() : null;
num2 = itr2.hasNext() ? itr2.next() : null;
count++;
}
// if this sum is greater than x, then
// move itr2 to next node
else if ((num1 + num2) > x)
num2 = itr2.hasNext() ? itr2.next() : null;
// else move itr1 to next node
else
num1 = itr1.hasNext() ? itr1.next() : null;
}
// required count of pairs
return count;
}
// Driver method
public static void main(String[] args)
{
Integer arr1[] = {3, 1, 5, 7};
Integer arr2[] = {8, 2, 5, 3};
// create linked list1 3->1->5->7
LinkedList<Integer> head1 = new LinkedList<>(Arrays.asList(arr1));
// create linked list2 8->2->5->3
LinkedList<Integer> head2 = new LinkedList<>(Arrays.asList(arr2));
int x = 10;
System.out.println("Count = " + countPairs(head1, head2, x));
}
}
Producción
Count = 2
Complejidad de tiempo: O(n1*logn1) + O(n2*logn2)
Espacio auxiliar: O(1)
Ordenar cambiará el orden de los Nodes. Si el orden es importante, se puede crear y utilizar una copia de las listas vinculadas.
Método 3 (hashing): la tabla hash se implementa utilizando unordered_set en C++ . Almacenamos todos los primeros elementos de la lista enlazada en la tabla hash. Para los elementos de la segunda lista enlazada, restamos cada elemento de x y verificamos el resultado en la tabla hash. Si el resultado está presente, incrementamos el conteo .
Implementación:
C++
// C++ implementation to count pairs from both linked
// lists whose sum is equal to a given value
#include <bits/stdc++.h>
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 sum is equal to a given value
int countPairs(struct Node* head1, struct Node* head2,
int x)
{
int count = 0;
unordered_set<int> us;
// insert all the elements of 1st list
// in the hash table(unordered_set 'us')
while (head1 != NULL)
{
us.insert(head1->data);
// move to next node
head1 = head1->next;
}
// for each element of 2nd list
while (head2 != NULL)
{
// find (x - head2->data) in 'us'
if (us.find(x - head2->data) != us.end())
count++;
// move to next node
head2 = head2->next;
}
// required count of pairs
return count;
}
// Driver program to test above
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 implementation to count pairs from both linked
// lists whose sum is equal to a given value
// Note : here we use java.util.LinkedList for
// linked list implementation
import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
class GFG
{
// method to count all pairs from both the linked lists
// whose sum is equal to a given value
static int countPairs(LinkedList<Integer> head1, LinkedList<Integer> head2, int x)
{
int count = 0;
HashSet<Integer> us = new HashSet<Integer>();
// insert all the elements of 1st list
// in the hash table(unordered_set 'us')
Iterator<Integer> itr1 = head1.iterator();
while (itr1.hasNext())
{
us.add(itr1.next());
}
Iterator<Integer> itr2 = head2.iterator();
// for each element of 2nd list
while (itr2.hasNext())
{
// find (x - head2->data) in 'us'
if (!(us.add(x - itr2.next())))
count++;
}
// required count of pairs
return count;
}
// Driver method
public static void main(String[] args)
{
Integer arr1[] = {3, 1, 5, 7};
Integer arr2[] = {8, 2, 5, 3};
// create linked list1 3->1->5->7
LinkedList<Integer> head1 = new LinkedList<>(Arrays.asList(arr1));
// create linked list2 8->2->5->3
LinkedList<Integer> head2 = new LinkedList<>(Arrays.asList(arr2));
int x = 10;
System.out.println("Count = " + countPairs(head1, head2, x));
}
}
Python3
# Python3 implementation to count pairs from both linked
# lists whose sum is equal to a given value
''' A Linked list node '''
class Node:
def __init__(self):
self.data = 0
self.next = None
# function to add a node at the
# beginning of the linked list
def push(head_ref, new_data):
''' allocate node '''
new_node =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 sum is equal to a given value
def countPairs(head1, head2, x):
count = 0;
us = set()
# add all the elements of 1st list
# in the hash table(unordered_set 'us')
while (head1 != None):
us.add(head1.data);
# move to next node
head1 = head1.next;
# for each element of 2nd list
while (head2 != None):
# find (x - head2.data) in 'us'
if ((x - head2.data) in us):
count += 1
# move to next node
head2 = head2.next;
# required count of pairs
return count;
# Driver program to test above
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 =", countPairs(head1, head2, x));
# This code is contributed by rutvik_56
C#
// C# implementation to count pairs from both linked
// lists whose sum is equal to a given value
// Note : here we use java.util.LinkedList for
// linked list implementation
using System;
using System.Collections.Generic;
class GFG
{
// method to count all pairs from both the linked lists
// whose sum is equal to a given value
static int countPairs(List<int> head1, List<int> head2, int x)
{
int count = 0;
HashSet<int> us = new HashSet<int>();
// insert all the elements of 1st list
// in the hash table(unordered_set 'us')
foreach(int itr1 in head1)
{
us.Add(itr1);
}
// for each element of 2nd list
foreach(int itr2 in head2)
{
// find (x - head2->data) in 'us'
if (!(us.Contains(x - itr2)))
count++;
}
// required count of pairs
return count;
}
// Driver code
public static void Main(String[] args)
{
int []arr1 = {3, 1, 5, 7};
int []arr2 = {8, 2, 5, 3};
// create linked list1 3->1->5->7
List<int> head1 = new List<int>(arr1);
// create linked list2 8->2->5->3
List<int> head2 = new List<int>(arr2);
int x = 10;
Console.WriteLine("Count = " + countPairs(head1, head2, x));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// JavaScript implementation to count pairs
// from both linked lists whose sum is equal
// to a given value
// A Linked list node
class Node
{
constructor(new_data)
{
this.data = new_data;
this.next = null;
}
};
// Function to count all pairs from both the linked
// lists whose sum is equal to a given value
function countPairs(head1, head2, x)
{
let count = 0;
let us = new Set();
// Insert all the elements of 1st list
// in the hash table(unordered_set 'us')
while (head1 != null)
{
us.add(head1.data);
// Move to next node
head1 = head1.next;
}
// For each element of 2nd list
while (head2 != null)
{
// Find (x - head2.data) in 'us'
if (us.has(x - head2.data))
count++;
// Move to next node
head2 = head2.next;
}
// Required count of pairs
return count;
}
// Driver code
let head1 = null;
let head2 = null;
// Create linked list1 3.1.5.7
head1 = new Node(3)
head1.next = new Node(1)
head1.next.next = new Node(5)
head1.next.next.next = new Node(7)
// Create linked list2 8.2.5.3
head2 = new Node(8)
head2.next = new Node(2)
head2.next.next = new Node(5)
head2.next.next.next = new Node(3)
let x = 10;
document.write("Count = " +
countPairs(head1, head2, x));
// This code is contributed by Potta Lokesh
</script>
Producción
Count = 2
Complejidad de tiempo: O (n1 + n2)
Espacio auxiliar: O (n1), se debe crear una tabla hash de la array que tenga un tamaño más pequeño para reducir la complejidad del espacio.
Este artículo es una contribución de Ayush Jauhari . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA