Two nodes in a Linked list whose product is equal to the target value
Given a head of a singly linked list and a target value. The task is to find whether there exist any two nodes in the linked list whose product is equal to the target value.
Examples:
Input: Linked-List = 2->5->3->4->6, Target = 12
Output: TrueInput: Linked-List = 1->4->3->7->2, Target = 5
Output: False
Approach: This can be solved with the following idea:
Using the Set data structure, check if the target is divided by a value in the linked list that is present or not. If present return true, otherwise return false.
Steps involved in the implementation of code:
- Declare a set seen.
- Iterate in a linked list:
- If target/ Curvalue is present in the set, return true.
- Otherwise, store the CurValue in the set.
- If no value is found after iterating return false.
Below is the implementation of the code:
C++
// C++ code for the above approach #include <bits/stdc++.h> using namespace std; // Structure of Linked List struct Node { int data; Node* next; Node( int x) { data = x; next = NULL; } }; // Function to check pair exists bool hasTwoNodesWithProduct(Node* head, int target) { // Declaration of set unordered_set< int > seen; Node* curr = head; // Iterate in linked list while (curr != NULL) { int currVal = curr->data; int product = target / currVal; // Check if value exist if (target % currVal == 0 && seen.find(product) != seen.end()) { return true ; } seen.insert(currVal); curr = curr->next; } // Pair doesn't exist return false ; } // Driver code int main() { // Formation of Linked List Node* head = new Node(2); head->next = new Node(5); head->next->next = new Node(3); head->next->next->next = new Node(4); head->next->next->next->next = new Node(6); int target = 12; // Function call cout << hasTwoNodesWithProduct(head, target) << endl; return 0; } // This code is contributed by omkar chavan |
Java
import java.util.*; // Structure of Linked List class Node { int data; Node next; Node( int x) { data = x; next = null ; } } class Main { // Function to check pair exists static boolean hasTwoNodesWithProduct(Node head, int target) { // Declaration of set HashSet<Integer> seen = new HashSet<>(); Node curr = head; // Iterate in linked list while (curr != null ) { int currVal = curr.data; int product = target / currVal; // Check if value exist if (target % currVal == 0 && seen.contains(product)) { return true ; } seen.add(currVal); curr = curr.next; } // Pair doesn't exist return false ; } // Driver code public static void main(String[] args) { // Formation of Linked List Node head = new Node( 2 ); head.next = new Node( 5 ); head.next.next = new Node( 3 ); head.next.next.next = new Node( 4 ); head.next.next.next.next = new Node( 6 ); int target = 12 ; // Function call System.out.println(hasTwoNodesWithProduct(head, target)); } } |
Python3
# Structure of Linked List class Node: def __init__( self , x): self .data = x self . next = None # Function to check pair exists def hasTwoNodesWithProduct(head, target): # Declaration of set seen = set () curr = head # Iterate in linked list while curr: currVal = curr.data product = target / / currVal # Check if value exist if target % currVal = = 0 and product in seen: return True seen.add(currVal) curr = curr. next # Pair doesn't exist return False # Driver code if __name__ = = '__main__' : # Formation of Linked List head = Node( 2 ) head. next = Node( 5 ) head. next . next = Node( 3 ) head. next . next . next = Node( 4 ) head. next . next . next . next = Node( 6 ) target = 12 # Function call print (hasTwoNodesWithProduct(head, target)) |
C#
using System; using System.Collections.Generic; public class Node { public int data; public Node next; // Constructor to initialize a new node public Node( int x) { data = x; next = null ; } } public class LinkedList { // Function to check if there exist two nodes in the // linked list whose product is equal to target public static bool HasTwoNodesWithProduct(Node head, int target) { // Declaration of set HashSet< int > seen = new HashSet< int >(); Node curr = head; // Iterate in linked list while (curr != null ) { int currVal = curr.data; int product = target / currVal; // Check if value exists if (target % currVal == 0 && seen.Contains(product)) { return true ; } seen.Add(currVal); curr = curr.next; } // Pair doesn't exist return false ; } // Driver code public static void Main( string [] args) { // Formation of Linked List Node head = new Node(2); head.next = new Node(5); head.next.next = new Node(3); head.next.next.next = new Node(4); head.next.next.next.next = new Node(6); int target = 12; // Function call Console.WriteLine( HasTwoNodesWithProduct(head, target)); } } |
Javascript
// Structure of Linked List class Node { constructor(x) { this .data = x; this .next = null ; } } // Function to check pair exists function hasTwoNodesWithProduct(head, target) { // Declaration of set const seen = new Set(); let curr = head; // Iterate in linked list while (curr !== null ) { const currVal = curr.data; const product = Math.floor(target / currVal); // Check if value exists if (target % currVal === 0 && seen.has(product)) { return true ; } seen.add(currVal); curr = curr.next; } // Pair doesn't exist return false ; } // Driver code function main() { // Formation of Linked List const head = new Node(2); head.next = new Node(5); head.next.next = new Node(3); head.next.next.next = new Node(4); head.next.next.next.next = new Node(6); const target = 12; // Function call console.log(hasTwoNodesWithProduct(head, target)); } // Run the main function main(); |
Output
1
Time Complexity: O(N)
Auxiliary Space: O(N)
Related Articles: