Given two linked lists, count pairs with sum X in C++

We are given a problem statement as: given two linked lists, count pairs with sum X in C++. Basically, we are given two linked lists and we have to count the number of such pairs, the sum of whose elements is equal to a given value X. There can be multiple approaches to solve this problem. Efficiency can vary if the initial lists are sorted.

Let us say we have two unsorted linked lists given as:

list1 = 6->5->4->7->2
list2 = 5->8->3->7->2
sum = 8

There are a total of two pairs (6,2) and (5,3)

We need to count the number of pairs whose sum is 8.

C++ program to count pairs with sum X from given two lists

A simple approach can be to iterate over two loops and check the sum of all the possible pairs. If we find any such pair whose sum is equal to the given value, we increase the counter by 1, else, we continue.

BRUTE FORCE

Approach:

  1. If any of the lists is null, we simply return 0 because our pair should have one element from each of the lists.
  2. Traverse one of the linked lists and for each element, traverse the second linked list to find its corresponding element.
  3. If such an element exists, increase the counter by 1.
  4. Return the count.

Note that the function count() is the actual solution. Rest all of the functions are used to create a linked list.

Code:

#include<iostream>

using namespace std;

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


node* creation(int x,node* list)
{
  node * temp = new node();
  node * nd = list;
  temp->data=x;
  temp->next=NULL;
  if(nd==NULL)
  {
    list=temp;
  }
  else
  {
    while(nd->next!=NULL)
    {
      nd = nd->next;
    }
    nd->next=temp;
  }
  return list;
}

void count(node* list1,node* list2,int sum){ 
    
    int cnt=0; 
    node *temp2=list2;
    if(list1==NULL || list2==NULL)
    {
        cout<<"0"<<endl ;
        return;
    }
 
    while(list1!=NULL)
    { 
        int num1=list1->data; 
        
        while(list2!=NULL)
        { 
            int num2=list2->data; 
            
            if(num1+num2==sum){ 
                cnt++; 
            }
 
            list2=list2->next; 
            
        }
        list2=temp2;
        list1=list1->next; 
        
    } 
     cout<<cnt<<endl; 
    
}

int main()
{
    node* list1 = NULL,*list2=NULL;
  list1=creation(6,list1);
  list1=creation(5,list1);
  list1=creation(7,list1);
  list1=creation(4,list1);
  list1=creation(2,list1);
  
  list2=creation(5,list2);
  list2=creation(8,list2);
  list2=creation(3,list2);
  list2=creation(7,list2);
  list2=creation(2,list2);
  
  count(list1,list2,8);
  return 0;
  
}

TIME COMPLEXITY: O(n1*n2)  where n1 =size of list1 and n2= size of list2.
SPACE COMPLEXITY: O(1)

EFFICIENT APPROACH USING HASHMAP

Instead of iterating over two loops, we can store the elements of the first list in a hashmap and then iterate over the second list to check if its corresponding element exits on the map or not.

Approach:

  1. We trade the time complexity with the space complexity. We use a hashmap to store the numbers of the first list.
    unordered_map<int,int> num2; 
    //store the values of the first list 
    while(list1!=NULL) { 
        num2[list1->data]++; 
        list1=list1->next; 
    }
  2. Then we iterate over the next list and check if the corresponding value exists in the hashmap or not.
    while(list2!=NULL) { 
        int left=sum-list2->data; 
        if(num2.find(left)!=num2.end()){ 
            cnt++; 
        } 
        list2=list2->next; 
    }
  3. We increment the counter if the pair exists.

Code:

#include<iostream>
#include<unordered_map>
using namespace std;

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


node* creation(int x,node* list)
{
  node * temp = new node();
  node * nd = list;
  temp->data=x;
  temp->next=NULL;
  if(nd==NULL)
  {
    list=temp;
  }
  else
  {
    while(nd->next!=NULL)
    {
      nd = nd->next;
    }
    nd->next=temp;
  }
  return list;
}

void count(node* list1,node* list2,int sum){ 
  int cnt=0;
 
  if(list1==NULL || list2==NULL)
  { 
      cout<<0<<endl; 
      return;
  } 
  unordered_map<int,int> num2; 

//store the values of the first list
  while(list1!=NULL)
  { 
      num2[list1->data]++; 
      list1=list1->next; 
  } 

//check for presence of the other element is the second list
  while(list2!=NULL)
  { 
      int left=sum-list2->data; 
      if(num2.find(left)!=num2.end()){ 
          cnt++; 
      }
 
      list2=list2->next;
  } 
     cout<<cnt<<endl; 
    
}

int main()
{
    node* list1 = NULL,*list2=NULL;
  list1=creation(6,list1);
  list1=creation(5,list1);
  list1=creation(7,list1);
  list1=creation(4,list1);
  list1=creation(2,list1);
  
  list2=creation(5,list2);
  list2=creation(8,list2);
  list2=creation(3,list2);
  list2=creation(7,list2);
  list2=creation(2,list2);
  
  count(list1,list2,8);
  return 0;
  
}

TIME COMPLEXITY: O(n1+n2)  where n1 =size of list1 and n2= size of list2 as we traverse both lists only once.
SPACE COMPLEXITY: O(n1) where n1 is the size of the first list.

SORTED LISTS

Another method that works with sorted lists is discussed below. Even if the lists are not sorted you can sort them first before applying this method. This method requires one list to be sorted in ascending order and the other to be sorted in descending order.

Approach:

  1. List1 is sorted in ascending order and list2 is sorted in descending order.
  2. Maintain two pointers, one for each list.
  3. Compare the sum at every step. If we get the sum, we move forward in both the lists and increase the count.
    if ((list1->data + list2->data) == sum) { 
        list1 = list1->next; 
        list2 = list2->next; 
        cnt++; 
    }
  4. If the sum is less than the given value increment the pointer of the ascending list. Step 4 and 5 is done to make our sum closer to the required sum.
    else if ((list1->data + list2->data) < sum) 
        list1 = list1->next;
  5. Else, if the sum is greater than the given value increment the pointer of the descending list.
    else 
        list2 = list2->next;
  6. We keep repeating the above steps until one of our lists become NULL.

Code:

#include<iostream>
using namespace std;

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


node* creation(int x,node* list)
{
  node * temp = new node();
  node * nd = list;
  temp->data=x;
  temp->next=NULL;
  if(nd==NULL)
  {
    list=temp;
  }
  else
  {
    while(nd->next!=NULL)
    {
      nd = nd->next;
    }
    nd->next=temp;
  }
  return list;
}
void count(node* list1,node* list2,int sum){ 
 int cnt = 0; 

    while (list1 != NULL && list2 != NULL) 
    { 
         
        if ((list1->data + list2->data) == sum) 
        { 
            list1 = list1->next; 
            list2 = list2->next; 
            cnt++;     
        }     
          
        else if ((list1->data + list2->data) < sum) 
            list1 = list1->next; 
                
        else
            list2 = list2->next;
    }
     cout<<cnt<<endl; 
    
}

int main()
{
    node* list1 = NULL,*list2=NULL;
  list1=creation(2,list1);
  list1=creation(4,list1);
  list1=creation(5,list1);
  list1=creation(6,list1);
  list1=creation(7,list1);
  
  list2=creation(8,list2);
  list2=creation(7,list2);
  list2=creation(5,list2);
  list2=creation(3,list2);
  list2=creation(2,list2);
  
  count(list1,list2,8);
  return 0;
  
}

TIME COMPLEXITY: O(n1+n2)  where n1 =size of list1 and n2= size of list2.
SPACE COMPLEXITY: O(1)

READ MORE:

Sorting an array using C++ inbuilt function
Count maximum points on same line in C++

 

Leave a Reply

Your email address will not be published. Required fields are marked *