Two nodes in a Linked list whose product is equal to the target value

By Ann Roberts On Mar 27, 2023

Improve Article

Save Article

Like Article

Improve Article

Save Article

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: True

Input: 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++

#include <bits/stdc++.h>

using namespace std;

struct Node {

int data;

Node* next;

Node(int x)

{

data = x;

next = NULL;

}

};

bool hasTwoNodesWithProduct(Node* head, int target)

{

unordered_set<int> seen;

Node* curr = head;

while (curr != NULL) {

int currVal = curr->data;

int product = target / currVal;

if (target % currVal == 0

&& seen.find(product) != seen.end()) {

return true;

}

seen.insert(currVal);

curr = curr->next;

}

return false;

}

int main()

{

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;

cout << hasTwoNodesWithProduct(head, target) << endl;

return 0;

}

Time Complexity: O(N)
Auxiliary Space: O(N)

Related Articles:

Improve Article

Save Article

Like Article

Improve Article

Save Article

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: True

Input: 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++

#include <bits/stdc++.h>

using namespace std;

struct Node {

int data;

Node* next;

Node(int x)

{

data = x;

next = NULL;

}

};

bool hasTwoNodesWithProduct(Node* head, int target)

{

unordered_set<int> seen;

Node* curr = head;

while (curr != NULL) {

int currVal = curr->data;

int product = target / currVal;

if (target % currVal == 0

&& seen.find(product) != seen.end()) {

return true;

}

seen.insert(currVal);

curr = curr->next;

}

return false;

}

int main()

{

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;

cout << hasTwoNodesWithProduct(head, target) << endl;

return 0;

}

Time Complexity: O(N)
Auxiliary Space: O(N)

Related Articles:

Read original article here

Denial of responsibility! Techno Blender is an automatic aggregator of the all world’s media. In each content, the hyperlink to the primary source is specified. All trademarks belong to their rightful owners, all materials to their authors. If you are the owner of the content and do not want us to publish your materials, please contact us by email – [email protected]. The content will be deleted within 24 hours.