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.

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;
};

void implementLinkedList(struct Node** headReference, int newItem)
{
    struct Node* newNode =	(struct Node*) malloc(sizeof(struct Node));

    newNode->data = newItem;

    newNode->next = (*headReference);

    (*headReference) = newNode;
}
int getPairOfsum (struct Node* head1, struct Node* head2,int sum)
{
    int count = 0;

    unordered_set<int> SET;

    while (head1 != NULL)
    {
        SET.insert(head1->data);

        head1 = head1->next;
    }

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

        head2 = head2->next;
    }
    return count;
}
int main()
{
    struct Node* head1 = NULL;
    struct Node* head2 = NULL;

    implementLinkedList (&head1,11);
    implementLinkedList (&head1, 6);
    implementLinkedList (&head1, 1);
    implementLinkedList (&head1, 8);

    implementLinkedList (&head2, 5);
    implementLinkedList (&head2, 3);
    implementLinkedList (&head2, 1);
    implementLinkedList (&head2, 9);

    int sum = 9;

    cout << "Count = "<< getPairOfsum (head1, head2, sum);
    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;
import java.util.LinkedList;

class PairOfSumInLinkedList1
{
    public static int getPairOfsum(LinkedList<Integer> head1, LinkedList<Integer> head2, int sum)
    {
        int count = 0;

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

        Iterator<Integer> itr1 = head1.iterator();
        while (itr1.hasNext())
        {
            SET.add(itr1.next());

        }

        Iterator<Integer> itr2 = head2.iterator();
        while (itr2.hasNext())
        {
            if (!(SET.add(sum - itr2.next())))
                count++;

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

        LinkedList<Integer> head1 = new LinkedList<>(Arrays.asList(arr1));

        LinkedList<Integer> head2 = new LinkedList<>(Arrays.asList(arr2));

        int x = 9;

        System.out.println("Count = " + getPairOfsum(head1, head2, x));
    }
}

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.

Space Complexity

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