Home Â» Technical Interview Questions Â» Hashing Interview Questions Â» 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

## Problem Statement

Problem “Count pairs from two linked lists whose sum is equal to a given value” state that you are given two linked lists and an integer value sum. The problem statement asked to find out how many total pair has a sum equal to the given value.

## Example

```LinkedList1 = 11 Ã  6 Ã  1 Ã  8

LinkedList2 = 5 Ã  3 Ã  1 Ã  9

Sum = 9```
`2`

Explanation: There are two pairs i.e, 6, 3, and 8, 1 that sums up the value to the given value 9.

## Algorithm to count pairs from linked lists whose sum is equal to a given value

```1. Push all the integer values to the two different linked lists.
2. Declare a set.
3. Set the count to 0.
4. Iterate over the first linked list and put all the values of it into the linked list1.
5. Iterate over the second linked list
1. Check if the set contains the difference between the value of x and a current element of linked list2.
1. If true then increase the value of count by 1.
6. Return count.```

### Explanation

We are given integer values as input. So, we will push them all into the linked lists. In C++, we have externally created a method for implementing a linked list to perform this solution. But in java, we have an in-built class of Linked List with the help of we can easily push all the integers values into the linked list. Now we have asked to find out the pair in both of the linked lists of which the number sums up to the given value.

READ  Find Top K (or Most Frequent) Numbers in a Stream

We are going to push all the integer values to the linked list. We are going to use Set Data Structure and will be traversing all the values of linked list1 and store all the values of the first linked list to set. Set also provides a feature that the common elements are automatically removed from the set. So if we next time we will be using the set there will no problem for the common elements, and also there will not be any of the common elements in there in the linked list.

Now we have all the values in linked list 1 into the set. Now we will traverse the second linked list and check if the difference between the x and each value of the second list is present in the set or not. If present then we have found a pair for now and also we will increase the value of count by 1. This means 1 pair found and it is counted. At the end of traversal. The value of count will be the number of pair which has sum equal to the given value.

## Code

### C++ to count pairs from two linked lists whose sum is equal to a given value

```#include<iostream>
#include<unordered_set>

using namespace std;

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

{
struct Node* newNode =	(struct Node*) malloc(sizeof(struct Node));

newNode->data = newItem;

}
{
int count = 0;

unordered_set<int> SET;

{

}

{
if (SET.find(sum - head2->data) != SET.end())
count++;

}
return count;
}
int main()
{

int sum = 9;

return 0;
}
```
`Count = 2`

### Java code to count pairs from two linked lists whose sum is equal to a given value

```import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;

{
{
int count = 0;

HashSet<Integer> SET = new HashSet<Integer>();

while (itr1.hasNext())
{

}

while (itr2.hasNext())
{
count++;

}
return count;
}
public static void main(String[] args)
{
Integer arr1[] = {11, 6, 1, 8};
Integer arr2[] = {5, 3, 1, 9};

int x = 9;

}
}
```
`Count = 2`

## Complexity Analysis

### Time Complexity

O(n1 + n2)Â whereÂ “n1”Â andÂ “n2”Â are the numbers of elements in the linked list. We are able to achieve linear time complexity. Because we traversed over both the linked lists and used HashSet.

READ  Longest Span with same Sum in two Binary arrays

### Space Complexity

Since we stored the input in two linked lists and used a HashSet. We have a linear space complexity solution.

 Array Interview Questions Graph Interview Questions LinkedList Interview Questions String Interview Questions Tree Interview Questions Core Java Interview Questions