Count pairs from two linked lists whose product is equal to a given value in C++

We are given with two linked lists and the task is to form the pairs using the integer elements of linked lists such that their product is equal to a given value which is let’s say, k. A linked list is a sequence of data structures, which are connected together via links.

Input 

vector v_1 = {5, 7, 8, 10, 11},. vector v_2 = {6, 4, 3, 2, 0} , int k = 20

Output 

Count of pairs from two linked lists whose product is equal to a given value k are: 2

Explanation 

The pairs which can be formed using the given linked lists are: (5, 6) = 30(not equals to k), (5, 4) = 20(equals to k), (5, 3) = 15(not equals to k), (5, 2) = 10(not equals to k), (5, 0) = 0(not equals to k), (7, 6) = 42(not equals to k), (7, 4) = 28(not equals to k), (7, 3) = 21(not equals to k), (7, 2) = 14(not equals to k), (7, 0) = 0(not equals to k), (8, 6) = 48(not equals to k), (8, 4) = 32(not equals to k), (8, 3) = 24(not equals to k), (8, 2) = 16(not equals to k), (8, 0) = 0(not equals to k), (10, 6) = 60(not equals to k), (10, 4) = 40(not equals to k), (10, 3) = 30(not equals to k), (10, 2) = 20(not equals to k), (10, 0) = 0(not equals to k), (11, 6) = 66(not equals to k), (11, 4) = 44(not equals to k), (11, 3) = 3(not equals to k), (11, 2) = 22(not equals to k), (11, 0) = 0(not equals to k). So, clearly there are 2 pairs which are equal to the given product.

Input 

vector v_1 = {2, 3, 5, 6},. vector v_2 = {6, 4, 3} , int k = 9

Output 

Count of pairs from two linked lists whose sum is equal to a given value k are: 1

Explanation 

The pairs which can be formed using the given linked lists are: (2, 6) = 12(not equals to k), (2, 4) = 8(not equals to k), (2, 3) = 6(not equals to k), (3, 6) = 18(not equals to k), (3, 4) = 12(not equals to k), (3, 3) = 9(equals to k), (5, 6) = 30(not equals to k), (5, 4) = 20(not equals to k), (5, 3) = 15(not equals to k), (6, 6) = 36(not equals to k), (6, 4) = 24(not equals to k), (6, 3) = 18(not equals to k),. So, clearly there is 1 pair which is equal to the given sum.

Approach used in the below program is as follows

• Input the value of k and integer type values into two vectors such that we can pass the vectors to form a linked list

• Create a function that will create a linked list using the vector passed as an argument to the function.

• Traverse the loop till the size of a vector and create a pointer object of class

  ListNode

  • Traverse the loop while ptr-> next not equals to NULL and set ptr to ptr->next

  • Inside the ptr->next set vector[i]

  • Return start

• Create a function that will return the count of pairs matching with the given product.

  • Take a temporary variable count and set it to 0

  • Create two pointer object i.e. *first_list for first linked list and *second_list for second linked list.

  • Start loop from start pointer of first list till the list is not empty

  • Inside the loop, start another loop from start pointer of second list till the list is not empty

  • Inside the loop, check IF (first_list->data * second_list->data) == k then increment the count by 1

  • Return the count

• Print the result.

Example

 Live Demo

#include<bits/stdc++.h> using namespace std; class ListNode{ public:    int data;    ListNode *next;    ListNode(int data){       this->data = data;       next = NULL;    } }; ListNode *CreateList(vector v){    ListNode *start = new ListNode(v[0]);    for (int i = 1; i < v.size(); i++){       ListNode *ptr = start;       while (ptr->next != NULL){          ptr = ptr->next;       }       ptr->next = new ListNode(v[i]);    }    return start; } int product_pair(ListNode *start_1, ListNode *start_2, int k){    int count = 0;    ListNode *first_list , *second_list;    for (first_list = start_1; first_list != NULL; first_list = first_list->next){       for (second_list = start_2; second_list != NULL; second_list = second_list->next){          if ((first_list->data * second_list->data) == k){             count++;          }       }    }    return count; } int main(){    vector<int> v_1 = {5, 7, 8, 10, 11};    ListNode* start_1 = CreateList(v_1);    vector v_2 = {6, 4, 3, 2, 0};    ListNode* start_2 = CreateList(v_2);    int k = 30;    cout<<"Count of pairs from two linked lists whose product is equal to a given value k are: "<<product_pair(start_1, start_2, k); }

Output

If we run the above code it will generate the following output −

Count of pairs from two linked lists whose product is equal to a given value k are: 2