Dada una lista enlazada y un producto K. La tarea es verificar si existen dos números en la lista enlazada cuyo producto es igual al número K dado. Si existen dos números, imprímalos. Si hay varias respuestas, imprima cualquiera de ellas.
Ejemplos :
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
Método 1 (fuerza bruta) : ejecute dos bucles anidados para generar todos los pares posibles de la lista enlazada y verifique si el producto de cualquier par coincide con el producto K dado.
A continuación se muestra la implementación del enfoque anterior:
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 product
import 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 list
and 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 Code
public 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 node
class 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 Code
if __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 product
using 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 list
and 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 Code
public 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>
Producción:
NO PAIR EXIST
Complejidad temporal: O(N 2 ), donde N es la longitud de la lista enlazada.
Método 2 (usando hash) :
- Tome una tabla hash.
- Ahora, comience a recorrer la lista vinculada y verifique si el producto dado es divisible por el elemento actual de la lista vinculada, también verifique si (K/current_element) de la lista vinculada está presente en una tabla hash o no.
- en caso afirmativo, devuelva «verdadero»; de lo contrario, inserte el elemento actual en la tabla hash y haga que un puntero transversal apunte al siguiente elemento de la lista vinculada.
A continuación se muestra la implementación del enfoque anterior:
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 product
bool 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 product
import 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 node
class 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 Code
if __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 product
using 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>
Producción:
2 12
Complejidad temporal : O(N)
Espacio auxiliar : O(N)
Publicación traducida automáticamente
Artículo escrito por VishalBachchas y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA