Given a linked list, and a product K. The task is to check if there exist two numbers in the linked list whose product is equal to the given number K. If there exist two numbers, print them. If there are multiple answers, print any of them.
Examples:
Input : List = 1 -> 2 -> 3 -> 4 -> 5 -> NULL
K = 2
Output : Pair is (1, 2)
Input : List = 10 -> 12 -> 31 -> 42 -> 53 -> NULL
K = 15
Output : No Pair Exists
Method 1 (Brute force): Run two nested loops to generate all possible pairs of the linked list and check if the product of any pair matches with the given product K.
Below is the implementation of the above approach:
C++
// CPP code to find the pair with given product#include <bits/stdc++.h>using namespace std;/* Link list node */struct Node { int data; struct Node* next;};/* Given a reference (pointer to pointer) to the head of a list and an int, push a new node on the front of the list. */void push(struct Node** head_ref, int new_data){ struct Node* new_node = new Node; new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node;}/* Takes head pointer of the linked list and product*/int check_pair_product(struct Node* head, int prod){ struct Node *p = head, *q; while (p != NULL) { q = p->next; while (q != NULL) { // check if both product is equal to // given product if ((p->data) * (q->data) == prod) { cout << p->data << " " << q->data; return true; } q = q->next; } p = p->next; } return 0;}/* Driver program to test above function */int main(){ /* Start with the empty list */ struct Node* head = NULL; /* Use push() to construct linked list*/ push(&head, 1); push(&head, 4); push(&head, 1); push(&head, 12); push(&head, 1); push(&head, 18); push(&head, 47); push(&head, 16); push(&head, 12); push(&head, 14); /* function to print the result*/ bool res = check_pair_product(head, 26); if (res == false) cout << "NO PAIR EXIST"; return 0;} |
Java
// A Java code to find the pair// with given productimport java.util.*;class GFG { /* Link list node */static class Node { int data; Node next;}static Node head;/* Given a reference (pointer to pointer) to the head of a list and an int, push a new node on the front of the list. */static void push(Node head_ref, int new_data){ Node new_node = new Node(); new_node.data = new_data; new_node.next = head_ref; head_ref = new_node; head = head_ref;}/* Takes head pointer of the linked listand product*/static boolean check_pair_product(Node head, int prod){ Node p = head, q; while (p != null) { q = p.next; while (q != null) { // check if both product is equal to // given product if ((p.data) * (q.data) == prod) { System.out.print(p.data + " " + q.data); return true; } q = q.next; } p = p.next; } return false;}// Driver Codepublic static void main(String[] args){ /* Start with the empty list */ head = null; /* Use push() to construct linked list*/ push(head, 1); push(head, 4); push(head, 1); push(head, 12); push(head, 1); push(head, 18); push(head, 47); push(head, 16); push(head, 12); push(head, 14); /* function to print the result*/ boolean res = check_pair_product(head, 26); if (res == false) System.out.println("NO PAIR EXIST");}}// This code is contributed by Rajput-Ji |
Python3
# Python3 code to find the pair with # given product # Link list nodeclass Node: def __init__(self, data, next): self.data = data self.next = next class LinkedList: def __init__(self): self.head = None # Push a new node on the front of the list. def push(self, new_data): new_node = Node(new_data, self.head) self.head = new_node # Takes head pointer of the linked # list and product def check_pair_product(self, prod): p = self.head while p != None: q = p.next while q != None: # Check if both product is equal # to given product if p.data * q.data == prod: print(p.data, q.data) return True q = q.next p = p.next return False# Driver Codeif __name__ == "__main__": # Start with the empty list linkedlist = LinkedList() # Use push() to construct linked list linkedlist.push(1) linkedlist.push(4) linkedlist.push(1) linkedlist.push(12) linkedlist.push(1) linkedlist.push(18) linkedlist.push(47) linkedlist.push(16) linkedlist.push(12) linkedlist.push(14) # function to print the result res = linkedlist.check_pair_product(26) if res == False: print("NO PAIR EXIST") # This code is contributed by Rituraj Jain |
C#
// A C# code to find the pair// with given productusing System;class GFG { /* Link list node */public class Node { public int data; public Node next;}static Node head;/* Given a reference (pointer to pointer) to the head of a list and an int, push a new node on the front of the list. */static void push(Node head_ref, int new_data){ Node new_node = new Node(); new_node.data = new_data; new_node.next = head_ref; head_ref = new_node; head = head_ref;}/* Takes head pointer of the linked listand product*/static Boolean check_pair_product(Node head, int prod){ Node p = head, q; while (p != null) { q = p.next; while (q != null) { // check if both product is equal to // given product if ((p.data) * (q.data) == prod) { Console.Write(p.data + " " + q.data); return true; } q = q.next; } p = p.next; } return false;}// Driver Codepublic static void Main(String[] args){ /* Start with the empty list */ head = null; /* Use push() to construct linked list*/ push(head, 1); push(head, 4); push(head, 1); push(head, 12); push(head, 1); push(head, 18); push(head, 47); push(head, 16); push(head, 12); push(head, 14); /* function to print the result*/ Boolean res = check_pair_product(head, 26); if (res == false) Console.WriteLine("NO PAIR EXIST");}}// This code is contributed by Rajput-Ji |
Javascript
<script>// A javascript code to find the pair// with given product /* Link list node */ class Node { constructor(val) { this.data = val; this.next = null; } } var head; /* * Given a reference (pointer to pointer) to the head of a list and an int, push * a new node on the front of the list. */ function push(head_ref , new_data) { var new_node = new Node(); new_node.data = new_data; new_node.next = head_ref; head_ref = new_node; head = head_ref; } /* * Takes head pointer of the linked list and product */ function check_pair_product(head , prod) { var p = head, q; while (p != null) { q = p.next; while (q != null) { // check if both product is equal to // given product if ((p.data) * (q.data) == prod) { document.write(p.data + " " + q.data); return true; } q = q.next; } p = p.next; } return false; } // Driver Code /* Start with the empty list */ head = null; /* Use push() to construct linked list */ push(head, 1); push(head, 4); push(head, 1); push(head, 12); push(head, 1); push(head, 18); push(head, 47); push(head, 16); push(head, 12); push(head, 14); /* function to print the result */ var res = check_pair_product(head, 26); if (res == false) document.write("NO PAIR EXIST");// This code contributed by Rajput-Ji</script> |
Output
NO PAIR EXIST
Time complexity: O(N2), where N is the length of the linked list.
Auxiliary Space: O(1)
Method 2 (using hashing):
- Take a hashtable.
- Now, start traversing the linked list and check if the given product is divisible by the current element of the linked list also check if (K/current_element) of the linked list is present in a hashtable or not.
- if yes, return “true” else insert the current element to the hashtable and make a traversing pointer point to the next element of linked list.
Below is the implementation of the above approach:
C++14
// CPP code to find the pair with given product#include <bits/stdc++.h>using namespace std;/* Link list node */struct Node { int data; struct Node* next;};/* Given a reference (pointer to pointer) to the head of a list and an int, push a new node on the front of the list. */void push(struct Node** head_ref, int new_data){ struct Node* new_node = new Node; new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node;}// Function to check if pair with the given product// exists in the list// Takes head pointer of the linked list and productbool check_pair_product(struct Node* head, int prod){ unordered_set<int> s; struct Node* p = head; while (p != NULL) { int curr = p->data; // Check if pair exits if ((prod % curr == 0) && (s.find(prod / curr) != s.end())) { cout << curr << " " << prod / curr; return true; } s.insert(p->data); p = p->next; } return false;}/* Driver program to test above function*/int main(){ /* Start with the empty list */ struct Node* head = NULL; /* Use push() to construct linked list */ push(&head, 1); push(&head, 2); push(&head, 1); push(&head, 12); push(&head, 1); push(&head, 18); push(&head, 47); push(&head, 16); push(&head, 12); push(&head, 14); /* function to print the result*/ bool res = check_pair_product(head, 24); if (res == false) cout << "NO PAIR EXIST"; return 0;} |
Java
// Java code to find the pair with given productimport java.util.*;class Solution { static final int MAX = 100000; /* Link list node */ static class Node { int data; Node next; } /* Given a reference (pointer to pointer) to the head of a list and an int, push a new node on the front of the list. */ static Node push(Node head_ref, int new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.next = (head_ref); (head_ref) = new_node; return head_ref; } // Function to check if pair with given product // exists in the list // Takes head pointer of the linked list and product static boolean check_pair_product(Node head, int prod) { Vector<Integer> s = new Vector<Integer>(); Node p = head; while (p != null) { int curr = p.data; // Check if pair exits if ((prod % curr == 0) && (s.contains(prod / curr))) { System.out.print(curr + " " + (prod / curr)); return true; } s.add(p.data); p = p.next; } return false; } /* Driver program to test above function*/ public static void main(String args[]) { /* Start with the empty list */ Node head = null; /* Use push() to construct linked list */ head = push(head, 1); head = push(head, 2); head = push(head, 1); head = push(head, 12); head = push(head, 1); head = push(head, 18); head = push(head, 47); head = push(head, 16); head = push(head, 12); head = push(head, 14); /* function to print the result*/ boolean res = check_pair_product(head, 24); if (res == false) System.out.println("NO PAIR EXIST"); }}// This code is contributed// by Arnab Kundu |
Python3
# Python3 code to find the pair with# given product # Link list nodeclass Node: def __init__(self, data, next): self.data = data self.next = next class LinkedList: def __init__(self): self.head = None # Push a new node on the front of the list. def push(self, new_data): new_node = Node(new_data, self.head) self.head = new_node # Checks if pair with given product # exists in the list or not def check_pair_product(self, prod): p = self.head s = set() while p != None: curr = p.data # Check if pair exits if (prod % curr == 0 and (prod // curr) in s): print(curr, prod // curr) return True; s.add(p.data); p = p.next; return False# Driver Codeif __name__ == "__main__": # Start with the empty list linkedlist = LinkedList() # Use push() to construct linked list linkedlist.push(1) linkedlist.push(2) linkedlist.push(1) linkedlist.push(12) linkedlist.push(1) linkedlist.push(18) linkedlist.push(47) linkedlist.push(16) linkedlist.push(12) linkedlist.push(14) # function to print the result res = linkedlist.check_pair_product(24) if res == False: print("NO PAIR EXIST") # This code is contributed by Rituraj Jain |
C#
// C# code to find the pair with given productusing System;using System.Collections.Generic;class GFG { static readonly int MAX = 100000; /* Link list node */ public class Node { public int data; public Node next; } /* Given a reference (pointer to pointer) to the head of a list and an int, push a new node on the front of the list. */ static Node push(Node head_ref, int new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.next = (head_ref); (head_ref) = new_node; return head_ref; } // Function to check if pair with given product // exists in the list // Takes head pointer of the linked list and product static bool check_pair_product(Node head, int prod) { List<int> s = new List<int>(); Node p = head; while (p != null) { int curr = p.data; // Check if pair exits if ((prod % curr == 0) && (s.Contains(prod / curr))) { Console.Write(curr + " " + (prod / curr)); return true; } s.Add(p.data); p = p.next; } return false; } /* Driver code*/ public static void Main(String[] args) { /* Start with the empty list */ Node head = null; /* Use push() to construct linked list */ head = push(head, 1); head = push(head, 2); head = push(head, 1); head = push(head, 12); head = push(head, 1); head = push(head, 18); head = push(head, 47); head = push(head, 16); head = push(head, 12); head = push(head, 14); /* function to print the result*/ bool res = check_pair_product(head, 24); if (res == false) Console.Write("NO PAIR EXIST"); }}// This code contributed by Rajput-Ji |
Javascript
<script> // JavaScript code to find the pair with given product var MAX = 100000; /* Link list node */ class Node { constructor() { this.data = 0; this.next = null; } } /* Given a reference (pointer to pointer) to the head of a list and an int, push a new node on the front of the list. */ function push(head_ref, new_data) { var new_node = new Node(); new_node.data = new_data; new_node.next = head_ref; head_ref = new_node; return head_ref; } // Function to check if pair with given product // exists in the list // Takes head pointer of the linked list and product function check_pair_product(head, prod) { var s = []; var p = head; while (p != null) { var curr = p.data; // Check if pair exits if (prod % curr == 0 && s.includes(prod / curr)) { document.write(curr + " " + prod / curr); return true; } s.push(p.data); p = p.next; } return false; } /* Driver code*/ /* Start with the empty list */ var head = null; /* Use push() to construct linked list */ head = push(head, 1); head = push(head, 2); head = push(head, 1); head = push(head, 12); head = push(head, 1); head = push(head, 18); head = push(head, 47); head = push(head, 16); head = push(head, 12); head = push(head, 14); /* function to print the result*/ var res = check_pair_product(head, 24); if (res == false) document.write("NO PAIR EXIST"); </script> |
Output
2 12
Complexity Analysis:
- Time complexity: O(N)
- Auxiliary complexity: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
