Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

Count pairs from two linked lists whose sum is equal to a given value

Last Updated on November 28, 2022 by Prepbytes

This blog will discuss an important problem of count pairs from two linked with given sum Such problems do come in interviews.
Before solving the problem, it’s recommended that a known basic traversal in the Linked List check Linked List.
In this blog, we dive deep into each detail to get a number of pairs from two linked lists whose sum is equal to a given value.
Let’s look at the problem statement of count pairs from two linked with given sum for a better understanding.

How to count pairs from two linked list with given sum

We will be given two linked lists and an integer target as input, and we need to count pairs of integers in both lists such that each element of the pair belongs to different lists and their sum is equal to the given target integer.

To understand the problem statement, let’s take an example.

If the linked lists given to us are 1→3→5→8→NULL, 6→4→1→NULL, and the target = 9. Then, according to the problem statement:

• We need to find pairs of integers such that each element of the pair belongs to a different list, and their sum is equal to 9.
• All such pairs are – (3,6), (8,1) and (5,4)
• There are three possible pairs, so; we need to print 3 as output, i.e., the total count of possible pairs.

At this point, we have understood the problem statement. Now we will try to formulate an approach for this problem.

Before moving to the approach section, try to think about how you can approach this problem.

• If stuck, no problem, we will thoroughly see how we can approach this problem in the next section.

Let’s move to the approach section.

Approach 1 of count pairs from two linked with given sum

The naive approach that comes to our mind is that first, select a node in the first list and for each selected node in the first list, iterate in the second list and check if the sum of node’s (selected node from first list + node from the second list) is equal to the target or not.

Time Complexity of count pairs from two linked with given sum: O(N2), N is the number of nodes in a list.
Space Complexity of count pairs from two linked with given sum: O(1)

The above approach gives the correct result, but its time complexity is high. Can we reduce the time complexity? Let us find out If we can do so in the below approach.

Approach 2 of count pairs from two linked with given sum

• In this approach, we store all elements of the first list in a HashSet.
• Then, we iterate on the elements of the second list and find if the difference in the value of the current element of the second list and target exists in hash or not.
• If it exists in the HashSet, then we will increase the count by one.

Algorithm of count pairs from two linked with given sum

1. Initialize a result variable with 0 and create an unordered set.
2. Push all elements of the first list in the set created above.
3. Run a while loop till head2 (pointer to the second list) is not NULL.

• Check if (target – head2->data) exists in the set or not

• If it exists then, increment the result by one.
• Move the pointer head2 forward by one node.

4. After the loop is executed, return result from the function.

Code Implementation of count pairs from two linked with given sum

```#include<stdio.h>
#include<stdlib.h>

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 */

/* move the head to point to the new node */
}

// function to count all pairs from both the linked
// lists whose sum is equal to a given value
int x)
{
int count = 0;

// sort head1 in ascending order and
// For simplicity both lists are considered to be
// sorted in the respective orders

// traverse both the lists from left to right
{
// if this sum is equal to 'x', then move both
// the lists to next nodes and increment 'count'
{
count++;
}

// if this sum is greater than x, then
// move head2 to next node

// else move head1 to next node
else
}

// required count of pairs
return count;
}

// Driver program to test above
int main()
{

// assumed to be in ascending order

// assumed to be in descending order

int x = 10;
printf("Count = %d",ans);
return 0;
}
```
```#include<bits/stdc++.h>
using namespace std;
class Node{
public:
int data;
Node* next;
Node(int x){
data = x;
next = NULL;
}
};

{
int result = 0;

unordered_set<int> hash_set;

//insert all elements of first list in
//the hash set
{
}

// iterate on each elements of second list
{
//find if (target - currentData) exists
//in the hashset
if (hash_set.find(target - head2->data) != hash_set.end())
result++;

}
// return the result
return result;
}
int main(void){
Node* first = NULL;
first = new Node(1);
first->next = new Node(3);
first->next->next = new Node(5);
first->next->next->next = new Node(8);

Node* second = NULL;
second = new Node(6);
second->next = new Node(4);
second->next->next = new Node(1);
cout<<"Count of pairs having sum "<<9<<" are: ";
cout<<countPairs(first,second,9);

}

```
```class Node
{
int data;
Node next;
Node(int data)
{
this.data=data;
}
}

public class CountParis
{
static int countPairs(Node first,Node second, int target)
{
int result = 0;

// iterate both lists
while (first != null && second != null)
{
//calculate 'sum'
int sum = first.data + second.data;
//if sum equals target, increase result by 1
//and move both pointers
if (sum == target)
{
first = first.next;
second = second.next;
result++;
}

// if sum is more than target, move
// second pointer
else if (sum > target)
second = second.next;

// else move first pointer
else
first = first.next;
}

// required count of pairs
return result;
}
public static void main(String[] args)
{
Node first=null;
first=new Node(1);
first.next=new Node(3);
first.next.next=new Node(5);
first.next.next.next=new Node(8);

Node second=new Node(6);
second.next=new Node(4);
second.next.next=new Node(1);

System.out.println("Count of pairs having sum 9 are:");
System.out.println(countPairs(first, second, 9));
}
}

```
```class Node:

def __init__(self):
self.data = 0
self.next = None

new_node =Node()
new_node.data = new_data

def countPairs(first, second, target):
result = 0

while first and second:

sum = first.data + second.data

if sum == target:
first = first.next
second = second.next
result += 1

elif sum > target:
second = second.next

else:
first = first.next

return result

if __name__=='__main__':

x = 9

```
``````Output
Count of pairs having sum 9 are: 3``````

Time Complexity of count pairs from two linked with given sum: O(n), n is the number of nodes in a list.

Space Complexity of count pairs from two linked with given sum: O(n), n is the number of nodes in a list.

In the above approach, we are using extra space to store the elements in a hash set. Can we reduce the extra space used? Let us find out If we can do so in the below approach.

Approach 3 of count pairs with given sum

• At first, we need to sort the first list in ascending order and the second list in descending order.
• The above step is performed so that we can predict whether moving forward in the lists is going to increase our current sum or decrease it.
• It is evident that moving forward in the first list is going to increase the pair sum, and moving forward in the second one is going to decrease it.
• Now, we will initialize two different pointers at the head of both lists.
• We will compute the sum pointed by the pointers in each step, and If the sum is equal to the target, we will increase our result by one and move both pointers simultaneously.
• If the sum is less than the target, we need to increase it so we will move the pointer of the first list forward by one node.
• Else, we will move the pointer of the second list by one node.

Algorithm count pairs with given sum

1. Sort the first list in ascending order and the second list in descending order.
2. Initialize a variable result by 0.
3. Run a while loop till any one of first or second becomes NULL.
4. Calculate sum as the sum of data of nodes pointed by first and second pointers.
5. If the sum is equal to the target, increase the result by one and move both pointers forward by one node.
6. If the sum is greater than the target, move the second pointer forward by one node.
7. Else, move the first pointer forward by one node.

Note: For simplicity, in dry run and code implementation, we took the first and the second linked lists, which are already sorted in ascending and descending order, respectively. If you want to know how to sort a linked list, please feel free to refer to this article for sorting related concepts of linked list. Also, inside the code implementation, we haven’t provided the sorting function (function to sort the linked list); if you want to take unsorted linked lists, please sort them in proper format (the first list will be sorted in ascending order and the second list in descending order) using code from the above-mentioned article, before passing them to countPairs() function in the code.

Also, note that to sort a linked list in descending order, you can first sort the linked list in ascending order, and then you can reverse the sorted linked list.

Code Implementation of count pairs from two linked with given sum

```
#include
#include
#include

struct Node {
int data;
struct Node* next;
};

/* Function to print nodes in
void printList(struct Node* node)
{
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
}

// The main function that
// takes an array of lists
// arr[0..last] and generates
// the sorted output
struct Node* mergeKLists(struct Node* arr[], int last)
{

// Traverse form second list to last
for (int i = 1; i <= last; i++) {
while (true) {
// head of both the lists,
// 0 and ith list.

// Break if list ended
break;

// Smaller than first element
}
else
// Traverse the first list
// Smaller than next element
break;
}
// go to next node

// if last node
break;
}
}
}
}

return arr[0];
}

// Utility function to create a new node.
struct Node* newNode(int data)
{
struct Node *temp = (struct Node *) malloc(sizeof(struct Node));
temp->data = data;
temp->next = NULL;
return temp;
}

// Driver program to test
// above functions
int main()
{
int k = 3;

// Number of elements in each list
int n = 4;

// an array of pointers storing the
struct Node* arr[k];

arr[0] = newNode(10);
arr[0]->next = newNode(30);
arr[0]->next->next = newNode(50);
arr[0]->next->next->next = newNode(70);

arr[1] = newNode(20);
arr[1]->next = newNode(40);
arr[1]->next->next = newNode(60);
arr[1]->next->next->next = newNode(80);

arr[2] = newNode(0);
arr[2]->next = newNode(90);
arr[2]->next->next = newNode(100);
arr[2]->next->next->next = newNode(11);

// Merge all lists
struct Node* head = mergeKLists(arr, k - 1);

return 0;
}

```
```#include<bits/stdc++.h>
using namespace std;
class Node{
public:
int data;
Node* next;
Node(int x){
data = x;
next = NULL;
}
};

int countPairs(Node* first, Node* second,int target)
{
int result = 0;

// iterate both lists
while (first != NULL && second != NULL)
{
//calculate 'sum'
int sum = first->data + second->data;

//if sum equals target, increase result by 1
//and move both pointers
if (sum == target)
{
first = first->next;
second = second->next;
result++;
}

// if sum is more than target, move
// second pointer
else if (sum > target)
second = second->next;

// else move first pointer
else
first = first->next;
}

// required count of pairs
return result;
}

int main(void){
Node* first = NULL;
first = new Node(1);
first->next = new Node(3);
first->next->next = new Node(5);
first->next->next->next = new Node(8);

Node* second = NULL;
second = new Node(6);
second->next = new Node(4);
second->next->next = new Node(1);
cout<<"Count of pairs having sum "<<9<<" are: ";
cout<<countPairs(first,second,9);

}

```
```import java.util.*;
class Node
{
int data;
Node next;
Node(int data)
{
this.data=data;
}
}

public class CountParis
{
{
int res=0;
HashSet<Integer> h=new HashSet<>();

{
}
{
{
res++;
}
}
return res;
}
public static void main(String[] args)
{
Node first=null;
first=new Node(1);
first.next=new Node(3);
first.next.next=new Node(5);
first.next.next.next=new Node(8);

Node second=new Node(6);
second.next=new Node(4);
second.next.next=new Node(1);

System.out.println("Count of pairs having sum 9 are:");
System.out.println(countPairs(first, second, 9));
}
}

```
```class Node:

def __init__(self):
self.data = 0
self.next = None

new_node =Node()
new_node.data = new_data

count = 0
us = set()

# add all the elements of 1st list
# in the hash table(unordered_set 'us')

# move to next node

# iterate on each element of 2nd list

# find (x - head2.data) in 'us'
if ((x - head2.data) in us):
count += 1

# move to next node

# return the count
return count

if __name__=='__main__':

x = 9

```
``````Output
Count of pairs having sum 9 are: 3``````

Time Complexity of count pairs from two linked with given sum: O(N log N), N is the number of nodes in the list

Space Complexity of count pairs from two linked with given sum: O(1)

Conclusion

So, this article taught us how to solve the problem of data structure, i.e., count pairs from two linked lists whose sum is equal to a given value. We also saw how to approach the problem using a naive approach followed by two efficient solutions. We discussed an iterative implementation and some basic traversal in linked lists using examples, pseudocode, and code in detail. If you want to solve more questions on Linked List, which is curated by our expert mentors at PrepBytes, you can follow this link Linked List.