Count pairs from two linked lists whose sum is equal to a given value
Count pairs from two linked lists whose sum is equal to a given value
In this problem, we have given two linked lists of size n1 and n2 with distinct elements and a value k. We need to count all pairs from both lists whose sum is equal to the value k.
Note: The pair has an element from each linked list.
Examples:
Input: list1 = 3 ->1 ->5 ->7
list2 = 8 ->2 ->5 ->3k = 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->12k = 9
Output: 5
Method 1:(Naive Approach)
In this method, we will use two loops to pick elements from both the linked lists and check whether the sum of the pair is equal to x or not.
C implementation to count pairs from both linked lists whose sum is equal to a given value
#include<stdio.h>
#include<stdlib.h>
struct node
{
int info;
struct node * next;
};
struct node * start1 = NULL, * start2 = NULL, * res = NULL;
intlen = 0, n;
// For inserting the elements in the linked list
void add(int item, struct node ** temp)
{
struct node * t, * p;
t = (struct node * )malloc( sizeof( struct node ));
if(*temp == NULL)
{
* temp = t;
(* temp) ->info = item;
(* temp) ->next = NULL;
return;
}
else
{
struct node * p = * temp;
while(p -> next != NULL)
{
p = p -> next;
}
p -> next = t;
p = p -> next;
p -> info = item;
p -> next = NULL;
}
}
// For counting pairs from two linked lists whose sum is equal to a given value
intcountPairs(struct node * head1, struct node * head2, int k)
{
int count = 0;
struct node * t1, * t2;
// traverse the 1st linked list
for (t1 = head1; t1 != NULL; t1 = t1 -> next)
for (t2 = head2; t2 != NULL; t2 = t2 -> next)
if ((t1 -> info + t2 -> info) == k)
count++;
return count;
}
// To display the elements of the linked list
void traverse(struct node * t)
{
if(t == NULL)
{
printf(" Linked list is empty\n");
}
while(t -> next != NULL)
{
printf("%d -> ", t -> info);
t = t -> next;
}
printf("%d\n", t -> info);
}
// Driver Function
int main()
{
int k;
printf("Enter the value of k:");
scanf("%d", &k);
// Add element into the linked1
add(4, &start1);
add(3, &start1);
add(5, &start1);
add(6, &start1);
add(9, &start1);
add(8, &start1);
// Add element into the linked2
add(1, &start2);
add(4, &start2);
add(3, &start2);
add(7, &start2);
add(9, &start2);
add(2, &start2);
int res = countPairs(start1, start2, k);
printf("count is:%d",res);
return 0;
}
Output:
Time Complexity: The time complexity of the above method is O(n1*n2).
Space Complexity:The space complexity of the above method is O(1) which is constant.
Method 2:(By Sorting)
This method will sort the 1st linked list in ascending order and the 2nd linked list in descending order. Then, we will traverse both the linked lists from left to right to count the pairs.
Note:Here, we assume that we have sorted linked lists.
#include<stdio.h>
#include<stdlib.h>
struct node
{
int info;
struct node * next;
};
struct node * start1 = NULL, * start2 = NULL, * res = NULL;
intlen = 0, n;
// For inserting the elements in the linked list
void add(int item, struct node ** temp)
{
struct node * t, * p;
t = (struct node * )malloc( sizeof( struct node ));
if(*temp == NULL)
{
* temp = t;
(* temp) ->info = item;
(* temp) ->next = NULL;
return;
}
else
{
struct node * p = * temp;
while(p -> next != NULL)
{
p = p -> next;
}
p -> next = t;
p = p -> next;
p -> info = item;
p -> next = NULL;
}
}
// For counting pairs from two linked lists whose sum is equal to a given value
intcountPairs(struct node * head1, struct node * head2, int k)
{
int count = 0;
while (head1 != NULL && head2 != NULL)
{
if ((head1->data + head2->data) == x)
{
head1 = head1->next;
head2 = head2->next;
count++;
}
else if ((head1->data + head2->data)> x)
head2 = head2->next;
else
head1 = head1 ->next;
}
return count;
}
// To display the elements of the linked list
void traverse(struct node * t)
{
if(t == NULL)
{
printf(" Linked list is empty\n");
}
while(t -> next != NULL)
{
printf("%d -> ", t -> info);
t = t -> next;
}
printf("%d\n", t -> info);
}
// Driver Function
int main()
{
int k;
printf("Enter the value of k:");
scanf("%d", &k);
// Add element into the linked1
add(3, &start1);
add(4, &start1);
add(5, &start1);
add(6, &start1);
add(8, &start1);
add(9, &start1);
// Add element into the linked2
add(9, &start2);
add(7, &start2);
add(4, &start2);
add(3, &start2);
add(2, &start2);
add(1, &start2);
int res = countPairs(start1, start2, k);
printf("count is:%d",res);
return 0;
}
Output:
Time Complexity: The time complexity of above method is O(n1 * logn1) +.O(n2 * logn2).
Space Complexity:The space complexity of the above method is O(1) which is constant.