Dada una lista ordenada doblemente enlazada de Nodes distintos (no hay dos Nodes que tengan los mismos datos) y un valor x. La tarea es contar los tripletes en la lista que producen hasta un valor x dado.
Ejemplos:
Entrada: lista = 1->2->4->5->6->8->9, x = 8
Salida: 1
triplete es (1, 2, 4)Entrada: lista = 1->2->4->5->6->8->9, x = 120
Salida: 1
triplete es (4, 5, 6)
Enfoque ingenuo: el uso de tres bucles anidados genera todos los tripletes y verifica si los elementos en el producto triplete hasta x o no.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to count triplets
// in a sorted doubly linked list
// whose product is equal to a given value 'x'
#include <bits/stdc++.h>
using namespace std;
// structure of node of doubly linked list
struct Node {
int data;
struct Node *next, *prev;
};
// function to count triplets in a sorted doubly linked list
// whose product is equal to a given value 'x'
int countTriplets(struct Node* head, int x)
{
struct Node *ptr1, *ptr2, *ptr3;
int count = 0;
// generate all possible triplets
for (ptr1 = head; ptr1 != NULL; ptr1 = ptr1->next)
for (ptr2 = ptr1->next; ptr2 != NULL; ptr2 = ptr2->next)
for (ptr3 = ptr2->next; ptr3 != NULL; ptr3 = ptr3->next)
// if elements in the current triplet product up to 'x'
if ((ptr1->data * ptr2->data * ptr3->data) == x)
// increment count
count++;
// required count of triplets
return count;
}
// A utility function to insert a new node at the
// beginning of doubly linked list
void insert(struct Node** head, int data)
{
// allocate node
struct Node* temp = new Node();
// put in the data
temp->data = data;
temp->next = temp->prev = NULL;
if ((*head) == NULL)
(*head) = temp;
else {
temp->next = *head;
(*head)->prev = temp;
(*head) = temp;
}
}
// Driver program to test above
int main()
{
// start with an empty doubly linked list
struct Node* head = NULL;
// insert values in sorted order
insert(&head, 9);
insert(&head, 8);
insert(&head, 6);
insert(&head, 5);
insert(&head, 4);
insert(&head, 2);
insert(&head, 1);
int x = 8;
cout << "Count = "
<< countTriplets(head, x);
return 0;
}
Java
// Java implementation to count triplets
// in a sorted doubly linked list
// whose sum is equal to a given value 'x'
import java.util.*;
// Represents node of a doubly linked list
class Node
{
public int data;
public Node prev, next;
public Node(int val)
{
data = val;
prev = null;
next = null;
}
}
class GFG
{
// function to count triplets in
// a sorted doubly linked list
// whose sum is equal to a given value 'x'
static int countTriplets(Node head, int x)
{
Node ptr1, ptr2, ptr3;
int count = 0;
// generate all possible triplets
for (ptr1 = head; ptr1 != null; ptr1 = ptr1.next)
for (ptr2 = ptr1.next; ptr2 != null; ptr2 = ptr2.next)
for (ptr3 = ptr2.next; ptr3 != null; ptr3 = ptr3.next)
// if elements in the current triplet sum up to 'x'
if ((ptr1.data * ptr2.data * ptr3.data) == x)
// increment count
count++;
// required count of triplets
return count;
}
// A utility function to insert a new node at the
// beginning of doubly linked list
static Node insert(Node head, int val)
{
// allocate node
Node temp = new Node(val);
if (head == null)
head = temp;
else
{
temp.next = head;
head.prev = temp;
head = temp;
}
return head;
}
// Driver code
public static void main(String []args)
{
// start with an empty doubly linked list
Node head = null;
// insert values in sorted order
head = insert(head, 9);
head = insert(head, 8);
head = insert(head, 6);
head = insert(head, 5);
head = insert(head, 4);
head = insert(head, 2);
head = insert(head, 1);
int x = 8;
System.out.println("count = " + countTriplets(head, x));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation to count triplets
# in a sorted doubly linked list
# whose sum is equal to a given value 'x'
# Represents node of a doubly linked list
class Node:
data = None
prev = None
next_ = None
def __init__(self, val):
self.data = val
self.prev = None
self.next_ = None
# function to count triplets in
# a sorted doubly linked list
# whose sum is equal to a given value 'x'
def countTriplets(head, x):
ptr1, ptr2, ptr3 = Node(0), Node(0), Node(0)
count = 0
# generate all possible triplets
ptr1 = head
while ptr1 is not None:
ptr2 = ptr1.next_
while ptr2 is not None:
ptr3 = ptr2.next_
while ptr3 is not None:
# if elements in the current
# triplet sum up to 'x'
if ptr1.data * ptr2.data * ptr3.data == x:
# increment count
count += 1
ptr3 = ptr3.next_
ptr2 = ptr2.next_
ptr1 = ptr1.next_
# required count of triplets
return count
# A utility function to insert a new node at the
# beginning of doubly linked list
def insert(head, val):
# allocate node
temp = Node(val)
if head is None:
head = temp
else:
temp.next_ = head
head.prev = temp
head = temp
return head
# Driver Code
if __name__ == "__main__":
# start with an empty doubly linked list
head = Node(0)
# insert values in sorted order
head = insert(head, 9)
head = insert(head, 8)
head = insert(head, 6)
head = insert(head, 5)
head = insert(head, 4)
head = insert(head, 2)
head = insert(head, 1)
x = 8
print("count =", countTriplets(head, x))
# This code is contributed by
# sanjeev2552
C#
// C# implementation to count triplets
// in a sorted doubly linked list
// whose sum is equal to a given value 'x'
using System;
// Represents node of a doubly linked list
public class Node
{
public int data;
public Node prev, next;
public Node(int val)
{
data = val;
prev = null;
next = null;
}
}
class GFG
{
// function to count triplets in
// a sorted doubly linked list
// whose sum is equal to a given value 'x'
static int countTriplets(Node head, int x)
{
Node ptr1, ptr2, ptr3;
int count = 0;
// generate all possible triplets
for (ptr1 = head; ptr1 != null; ptr1 = ptr1.next)
for (ptr2 = ptr1.next; ptr2 != null; ptr2 = ptr2.next)
for (ptr3 = ptr2.next; ptr3 != null; ptr3 = ptr3.next)
// if elements in the current triplet sum up to 'x'
if ((ptr1.data * ptr2.data * ptr3.data) == x)
// increment count
count++;
// required count of triplets
return count;
}
// A utility function to insert a new node at the
// beginning of doubly linked list
static Node insert(Node head, int val)
{
// allocate node
Node temp = new Node(val);
if (head == null)
head = temp;
else
{
temp.next = head;
head.prev = temp;
head = temp;
}
return head;
}
// Driver code
public static void Main(String []args)
{
// start with an empty doubly linked list
Node head = null;
// insert values in sorted order
head = insert(head, 9);
head = insert(head, 8);
head = insert(head, 6);
head = insert(head, 5);
head = insert(head, 4);
head = insert(head, 2);
head = insert(head, 1);
int x = 8;
Console.WriteLine("count = " + countTriplets(head, x));
}
}
// This code is contributed by Arnab Kundu
Javascript
<script>
// javascript implementation to count triplets
// in a sorted doubly linked list
// whose sum is equal to a given value 'x' // Represents node of a doubly linked list
class Node {
constructor(val) {
this.data = val;
this.prev = null;
this.next = null;
}
}
// function to count triplets in
// a sorted doubly linked list
// whose sum is equal to a given value 'x'
function countTriplets( head , x) {
var ptr1, ptr2, ptr3;
var count = 0;
// generate all possible triplets
for (ptr1 = head; ptr1 != null; ptr1 = ptr1.next)
for (ptr2 = ptr1.next; ptr2 != null; ptr2 = ptr2.next)
for (ptr3 = ptr2.next; ptr3 != null; ptr3 = ptr3.next)
// if elements in the current triplet sum up to 'x'
if ((ptr1.data * ptr2.data * ptr3.data) == x)
// increment count
count++;
// required count of triplets
return count;
}
// A utility function to insert a new node at the
// beginning of doubly linked list
function insert( head , val) {
// allocate node
temp = new Node(val);
if (head == null)
head = temp;
else {
temp.next = head;
head.prev = temp;
head = temp;
}
return head;
}
// Driver code
// start with an empty doubly linked list
head = null;
// insert values in sorted order
head = insert(head, 9);
head = insert(head, 8);
head = insert(head, 6);
head = insert(head, 5);
head = insert(head, 4);
head = insert(head, 2);
head = insert(head, 1);
var x = 8;
document.write("count = " + countTriplets(head, x));
// This code contributed by umadevi9616
</script>
Producción:
Count = 1
Complejidad de tiempo: O(n^3)
Espacio auxiliar: O(1)
Método 2 (hashing): cree una tabla hash con tuplas (clave, valor) representadas como tuplas (datos de Node, puntero de Node). Recorra la lista doblemente enlazada y almacene los datos de cada Node y su par de punteros (tupla) en la tabla hash. Ahora, genera cada posible par de Nodes. Para cada par de Nodes, calcule p_product (producto de datos en los dos Nodes) y verifique si (x/p_product) existe en la tabla hash o no. Si existe, también verifique que los dos Nodes en el par no sean los mismos que el Node asociado con (x/p_product) en la tabla hash y finalmente incremente el conteo. Regresar (contar/3) ya que cada triplete se cuenta 3 veces en el proceso anterior.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to count triplets
// in a sorted doubly linked list
// whose product is equal to a given value 'x'
#include <bits/stdc++.h>
using namespace std;
// structure of node of doubly linked list
struct Node {
int data;
struct Node *next, *prev;
};
// function to count triplets in a sorted doubly linked list
// whose product is equal to a given value 'x'
int countTriplets(struct Node* head, int x)
{
struct Node *ptr, *ptr1, *ptr2;
int count = 0;
// unordered_map 'um' implemented as hash table
unordered_map<int, Node*> um;
// insert the <node data, node pointer> tuple in 'um'
for (ptr = head; ptr != NULL; ptr = ptr->next)
um[ptr->data] = ptr;
// generate all possible pairs
for (ptr1 = head; ptr1 != NULL; ptr1 = ptr1->next)
for (ptr2 = ptr1->next; ptr2 != NULL; ptr2 = ptr2->next) {
// p_product = product of elements in the current pair
int p_product = (ptr1->data * ptr2->data);
// if 'x/p_product' is present in 'um' and
// either of the two nodes
// are not equal to the 'um[x/p_product]' node
if (um.find(x / p_product) != um.end() && um[x / p_product] != ptr1
&& um[x / p_product] != ptr2)
// increment count
count++;
}
// required count of triplets
// division by 3 as each triplet is counted 3 times
return (count / 3);
}
// A utility function to insert a new node at the
// beginning of doubly linked list
void insert(struct Node** head, int data)
{
// allocate node
struct Node* temp = new Node();
// put in the data
temp->data = data;
temp->next = temp->prev = NULL;
if ((*head) == NULL)
(*head) = temp;
else {
temp->next = *head;
(*head)->prev = temp;
(*head) = temp;
}
}
// Driver program to test above functions
int main()
{
// start with an empty doubly linked list
struct Node* head = NULL;
// insert values in sorted order
insert(&head, 9);
insert(&head, 8);
insert(&head, 6);
insert(&head, 5);
insert(&head, 4);
insert(&head, 2);
insert(&head, 1);
int x = 8;
cout << "Count = "
<< countTriplets(head, x);
return 0;
}
Java
// Java implementation to count triplets
// in a sorted doubly linked list whose
// product is equal to a given value 'x'
import java.io.*;
import java.util.*;
// Structure of node of doubly linked list
class Node
{
int data;
Node next, prev;
}
class GFG{
// Function to count triplets in a sorted
// doubly linked list whose product is
// equal to a given value 'x'
static int countTriplets(Node head, int x)
{
Node ptr, ptr1, ptr2;
int count = 0;
// Unordered_map 'um' implemented
// as hash table
Map<Integer,
Node> um = new HashMap<Integer,
Node>();
// Insert the <node data, node pointer>
// tuple in 'um'
for(ptr = head; ptr != null; ptr = ptr.next)
{
um.put(ptr.data, ptr);
}
// Generate all possible pairs
for(ptr1 = head;
ptr1 != null;
ptr1 = ptr1.next)
{
for(ptr2 = ptr1.next;
ptr2 != null;
ptr2 = ptr2.next)
{
// p_product = product of elements
// in the current pair
int p_product = (ptr1.data * ptr2.data);
// If 'x/p_product' is present in 'um' and
// either of the two nodes are not equal
// to the 'um[x/p_product]' node
if (um.containsKey(x / p_product) &&
um.get(x / p_product) != ptr1 &&
um.get(x / p_product) != ptr2)
{
// Increment count
count++;
}
}
}
// Required count of triplets
// division by 3 as each triplet
// is counted 3 times
return (count / 3);
}
// A utility function to insert a new
// node at the beginning of doubly linked list
static Node insert(Node head, int data)
{
// Allocate node
Node temp = new Node();
// Put in the data
temp.data = data;
temp.next = temp.prev = null;
if (head == null)
{
head = temp;
}
else
{
temp.next = head;
head.prev = temp;
head = temp;
}
return head;
}
// Driver code
public static void main(String[] args)
{
// Start with an empty doubly linked list
Node head = null;
// Insert values in sorted order
head = insert(head, 9);
head = insert(head, 8);
head = insert(head, 6);
head = insert(head, 5);
head = insert(head, 4);
head = insert(head, 2);
head = insert(head, 1);
int x = 8;
System.out.println("Count = " +
countTriplets(head, x));
}
}
// This code is contributed by avanitrachhadiya2155
Python3
# Python3 implementation to
# count triplets in a sorted
# doubly linked list whose
# product is equal to a given
# value 'x'
from math import ceil
# structure of node of doubly
# linked list
class Node:
def __init__(self, x):
self.data = x
self.next = None
self.prev = None
# function to count triplets
# in a sorted doubly linked
# list whose product is equal
# to a given value 'x'
def countTriplets(head, x):
ptr, ptr1, ptr2 = None, None, None
count = 0
# unordered_map 'um' implemented
# as hash table
um = {}
# insert the tuple in 'um'
ptr = head
while ptr != None:
um[ptr.data] = ptr
ptr = ptr.next
# generate all possible pairs
ptr1 = head
while ptr1 != None:
ptr2 = ptr1.next
while ptr2 != None:
# p_product = product of
# elements in the current
# pair
p_product = (ptr1.data *
ptr2.data)
# if 'x/p_product' is present
# in 'um' and either of the
# two nodes are not equal to
# the 'um[x/p_product]' node
if ((x / p_product) in um and
(x / p_product) != ptr1 and
um[x / p_product] != ptr2):
# increment count
count += 1
ptr2 = ptr2.next
ptr1 = ptr1.next
# required count of triplets
# division by 3 as each triplet
# is counted 3 times
return (count // 3)
# A utility function to insert a
# new node at the beginning of
# doubly linked list
def insert(head, data):
# allocate node
temp = Node(data)
# put in the data
temp.data = data
temp.next = temp.prev = None
if (head == None):
head = temp
else:
temp.next = head
head.prev = temp
head = temp
return head
# Driver code
if __name__ == '__main__':
# start with an empty
# doubly linked list
head = None
# insert values in sorted
# order
head = insert(head, 9)
head = insert(head, 8)
head = insert(head, 6)
head = insert(head, 5)
head = insert(head, 4)
head = insert(head, 2)
head = insert(head, 1)
x = 8
print("Count =",
countTriplets(head, x))
# This code is contributed by Mohit Kumar 29
C#
// C# implementation to count triplets
// in a sorted doubly linked list whose
// product is equal to a given value 'x'
using System;
using System.Collections.Generic;
// Structure of node of doubly linked list
class Node
{
public int data;
public Node next, prev;
}
class GFG
{
// Function to count triplets in a sorted
// doubly linked list whose product is
// equal to a given value 'x'
static int countTriplets(Node head, int x)
{
Node ptr, ptr1, ptr2;
int count = 0;
// Unordered_map 'um' implemented
// as hash table
Dictionary<int, Node> um = new Dictionary<int, Node>();
// Insert the <node data, node pointer>
// tuple in 'um'
for(ptr = head; ptr != null; ptr = ptr.next)
{
um.Add(ptr.data, ptr);
}
// Generate all possible pairs
for(ptr1 = head;
ptr1 != null;
ptr1 = ptr1.next)
{
for(ptr2 = ptr1.next;
ptr2 != null;
ptr2 = ptr2.next)
{
// p_product = product of elements
// in the current pair
int p_product = (ptr1.data * ptr2.data);
// If 'x/p_product' is present in 'um' and
// either of the two nodes are not equal
// to the 'um[x/p_product]' node
if (um.ContainsKey(x / p_product) &&
um[x / p_product] != ptr1 &&
um[x / p_product] != ptr2)
{
// Increment count
count++;
}
}
}
// Required count of triplets
// division by 3 as each triplet
// is counted 3 times
return (count / 3);
}
// A utility function to insert a new
// node at the beginning of doubly linked list
static Node insert(Node head, int data)
{
// Allocate node
Node temp = new Node();
// Put in the data
temp.data = data;
temp.next = temp.prev = null;
if (head == null)
{
head = temp;
}
else
{
temp.next = head;
head.prev = temp;
head = temp;
}
return head;
}
// Driver code
static public void Main ()
{
// Start with an empty doubly linked list
Node head = null;
// Insert values in sorted order
head = insert(head, 9);
head = insert(head, 8);
head = insert(head, 6);
head = insert(head, 5);
head = insert(head, 4);
head = insert(head, 2);
head = insert(head, 1);
int x = 8;
Console.WriteLine("Count = " + countTriplets(head, x));
}
}
// This code is contributed by rag2127
Javascript
<script>
// JavaScript implementation to count triplets
// in a sorted doubly linked list whose
// product is equal to a given value 'x'
class Node
{
constructor(data)
{
this.data=data;
this.next=this.prev=null;
}
}
// Function to count triplets in a sorted
// doubly linked list whose product is
// equal to a given value 'x'
function countTriplets(head,x)
{
let ptr, ptr1, ptr2;
let count = 0;
// Unordered_map 'um' implemented
// as hash table
let um = new Map();
// Insert the <node data, node pointer>
// tuple in 'um'
for(ptr = head; ptr != null; ptr = ptr.next)
{
um.set(ptr.data, ptr);
}
// Generate all possible pairs
for(ptr1 = head;
ptr1 != null;
ptr1 = ptr1.next)
{
for(ptr2 = ptr1.next;
ptr2 != null;
ptr2 = ptr2.next)
{
// p_product = product of elements
// in the current pair
let p_product = (ptr1.data * ptr2.data);
// If 'x/p_product' is present in 'um' and
// either of the two nodes are not equal
// to the 'um[x/p_product]' node
if (um.has(x / p_product) &&
um.get(x / p_product) != ptr1 &&
um.get(x / p_product) != ptr2)
{
// Increment count
count++;
}
}
}
// Required count of triplets
// division by 3 as each triplet
// is counted 3 times
return (count / 3);
}
// A utility function to insert a new
// node at the beginning of doubly linked list
function insert(head,data)
{
// Allocate node
let temp = new Node();
// Put in the data
temp.data = data;
temp.next = temp.prev = null;
if (head == null)
{
head = temp;
}
else
{
temp.next = head;
head.prev = temp;
head = temp;
}
return head;
}
// Driver code
// Start with an empty doubly linked list
let head = null;
// Insert values in sorted order
head = insert(head, 9);
head = insert(head, 8);
head = insert(head, 6);
head = insert(head, 5);
head = insert(head, 4);
head = insert(head, 2);
head = insert(head, 1);
let x = 8;
document.write("Count = " +
countTriplets(head, x));
// This code is contributed by patel2127
</script>
Producción:
Count = 1
Complejidad de tiempo: O(n^2)
Espacio auxiliar: O(n)
Método-3 (Uso de dos punteros): Atraviese la lista doblemente enlazada de izquierda a derecha. Para cada Node actual durante el recorrido, inicialice dos punteros primero = puntero al Node al lado del Node actual y último = puntero al último Node de la lista. Ahora, cuente los pares en la lista desde el primero hasta el último puntero que produce hasta el valor (x / datos del Node actual) (algoritmo descrito en esta publicación). Agregue este conteo al total_count de trillizos. El puntero al último Node se puede encontrar solo una vez al principio.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to count triplets
// in a sorted doubly linked list
// whose product is equal to a given value 'x'
#include <bits/stdc++.h>
using namespace std;
// structure of node of doubly linked list
struct Node {
int data;
struct Node *next, *prev;
};
// function to count pairs whose product equal to given 'value'
int countPairs(struct Node* first, struct Node* second, int value)
{
int count = 0;
// The loop terminates when either of two pointers
// become NULL, or they cross each other (second->next
// == first), or they become same (first == second)
while (first != NULL && second != NULL && first != second
&& second->next != first) {
// pair found
if ((first->data * second->data) == value) {
// increment count
count++;
// move first in forward direction
first = first->next;
// move second in backward direction
second = second->prev;
}
// if product is greater than 'value'
// move second in backward direction
else if ((first->data * second->data) > value)
second = second->prev;
// else move first in forward direction
else
first = first->next;
}
// required count of pairs
return count;
}
// function to count triplets in a sorted doubly linked list
// whose product is equal to a given value 'x'
int countTriplets(struct Node* head, int x)
{
// if list is empty
if (head == NULL)
return 0;
struct Node *current, *first, *last;
int count = 0;
// get pointer to the last node of
// the doubly linked list
last = head;
while (last->next != NULL)
last = last->next;
// traversing the doubly linked list
for (current = head; current != NULL; current = current->next) {
// for each current node
first = current->next;
// count pairs with product(x / current->data) in the range
// first to last and add it to the 'count' of triplets
count += countPairs(first, last, x / current->data);
}
// required count of triplets
return count;
}
// A utility function to insert a new node at the
// beginning of doubly linked list
void insert(struct Node** head, int data)
{
// allocate node
struct Node* temp = new Node();
// put in the data
temp->data = data;
temp->next = temp->prev = NULL;
if ((*head) == NULL)
(*head) = temp;
else {
temp->next = *head;
(*head)->prev = temp;
(*head) = temp;
}
}
// Driver program to test above
int main()
{
// start with an empty doubly linked list
struct Node* head = NULL;
// insert values in sorted order
insert(&head, 9);
insert(&head, 8);
insert(&head, 6);
insert(&head, 5);
insert(&head, 4);
insert(&head, 2);
insert(&head, 1);
int x = 8;
cout << "Count = "
<< countTriplets(head, x);
return 0;
}
Java
// Java implementation to count triplets
// in a sorted doubly linked list
// whose product is equal to a given value 'x'
import java.util.*;
class GFG
{
// structure of node of doubly linked list
static class Node
{
int data;
Node next, prev;
};
// function to count pairs whose product
// equal to given 'value'
static int countPairs(Node first, Node second,
int value)
{
int count = 0;
// The loop terminates when either of two pointers
// become null, or they cross each other (second.next
// == first), or they become same (first == second)
while (first != null && second != null &&
first != second && second.next != first)
{
// pair found
if ((first.data * second.data) == value)
{
// increment count
count++;
// move first in forward direction
first = first.next;
// move second in backward direction
second = second.prev;
}
// if product is greater than 'value'
// move second in backward direction
else if ((first.data * second.data) > value)
second = second.prev;
// else move first in forward direction
else
first = first.next;
}
// required count of pairs
return count;
}
// function to count triplets in
// a sorted doubly linked list
// whose product is equal to a given value 'x'
static int countTriplets(Node head, int x)
{
// if list is empty
if (head == null)
return 0;
Node current, first, last;
int count = 0;
// get pointer to the last node of
// the doubly linked list
last = head;
while (last.next != null)
last = last.next;
// traversing the doubly linked list
for (current = head; current != null;
current = current.next)
{
// for each current node
first = current.next;
// count pairs with product(x / current.data)
// in the range first to last and
// add it to the 'count' of triplets
count += countPairs(first, last, x / current.data);
}
// required count of triplets
return count;
}
// A utility function to insert a new node at the
// beginning of doubly linked list
static Node insert(Node head, int data)
{
// allocate node
Node temp = new Node();
// put in the data
temp.data = data;
temp.next = temp.prev = null;
if ((head) == null)
(head) = temp;
else
{
temp.next = head;
(head).prev = temp;
(head) = temp;
}
return head;
}
// Driver code
public static void main(String args[])
{
// start with an empty doubly linked list
Node head = null;
// insert values in sorted order
head = insert(head, 9);
head = insert(head, 8);
head = insert(head, 6);
head = insert(head, 5);
head = insert(head, 4);
head = insert(head, 2);
head = insert(head, 1);
int x = 8;
System.out.println( "Count = "+ countTriplets(head, x));
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 implementation to count triplets # in a sorted doubly linked list whose # product is equal to a given value 'x' # Structure of node of doubly linked list class Node: def __init__(self, data): self.data = data self.next = None self.prev = None # Function to count pairs whose product # equal to given 'value' def countPairs(first, second, value): count = 0 # The loop terminates when either of two pointers # become None, or they cross each other (second.next # == first), or they become same (first == second) while (first != None and second != None and first != second and second.next != first): # Pair found if ((first.data * second.data) == value): # Increment count count += 1 # Move first in forward direction first = first.next # Move second in backward direction second = second.prev # If product is greater than 'value' # move second in backward direction elif ((first.data * second.data) > value): second = second.prev # Else move first in forward direction else: first = first.next # Required count of pairs return count # Function to count triplets in a sorted # doubly linked list whose product is # equal to a given value 'x' def countTriplets(head, x): # If list is empty if (head == None): return 0 count = 0 # Get pointer to the last node of # the doubly linked list last = head while (last.next != None): last = last.next current = head # Traversing the doubly linked list while current != None: # For each current node first = current.next # Count pairs with product(x / current.data) # in the range first to last and # add it to the 'count' of triplets count += countPairs(first, last, x // current.data) current = current.next # Required count of triplets return count # A utility function to insert a new node # at the beginning of doubly linked list def insert(head, data): # Allocate node temp = Node(data) # Put in the data temp.data = data temp.next = temp.prev = None if ((head) == None): (head) = temp else: temp.next = head (head).prev = temp (head) = temp return head # Driver code if __name__=='__main__': # Start with an empty doubly linked list head = None # Insert values in sorted order head = insert(head, 9) head = insert(head, 8) head = insert(head, 6) head = insert(head, 5) head = insert(head, 4) head = insert(head, 2) head = insert(head, 1) x = 8 print( "Count = " + str(countTriplets(head, x))) # This code is contributed by rutvik_56
C#
// C# implementation to count triplets
// in a sorted doubly linked list
// whose product is equal to a given value 'x'
using System;
class GFG
{
// structure of node of doubly linked list
class Node
{
public int data;
public Node next, prev;
};
// function to count pairs whose product
// equal to given 'value'
static int countPairs(Node first, Node second,
int value)
{
int count = 0;
// The loop terminates when either of two pointers
// become null, or they cross each other (second.next
// == first), or they become same (first == second)
while (first != null && second != null &&
first != second && second.next != first)
{
// pair found
if ((first.data * second.data) == value)
{
// increment count
count++;
// move first in forward direction
first = first.next;
// move second in backward direction
second = second.prev;
}
// if product is greater than 'value'
// move second in backward direction
else if ((first.data * second.data) > value)
second = second.prev;
// else move first in forward direction
else
first = first.next;
}
// required count of pairs
return count;
}
// function to count triplets in
// a sorted doubly linked list
// whose product is equal to a given value 'x'
static int countTriplets(Node head, int x)
{
// if list is empty
if (head == null)
return 0;
Node current, first, last;
int count = 0;
// get pointer to the last node of
// the doubly linked list
last = head;
while (last.next != null)
last = last.next;
// traversing the doubly linked list
for (current = head; current != null;
current = current.next)
{
// for each current node
first = current.next;
// count pairs with product(x / current.data)
// in the range first to last and
// add it to the 'count' of triplets
count += countPairs(first, last, x / current.data);
}
// required count of triplets
return count;
}
// A utility function to insert a new node at the
// beginning of doubly linked list
static Node insert(Node head, int data)
{
// allocate node
Node temp = new Node();
// put in the data
temp.data = data;
temp.next = temp.prev = null;
if ((head) == null)
(head) = temp;
else
{
temp.next = head;
(head).prev = temp;
(head) = temp;
}
return head;
}
// Driver code
public static void Main(String []args)
{
// start with an empty doubly linked list
Node head = null;
// insert values in sorted order
head = insert(head, 9);
head = insert(head, 8);
head = insert(head, 6);
head = insert(head, 5);
head = insert(head, 4);
head = insert(head, 2);
head = insert(head, 1);
int x = 8;
Console.WriteLine( "Count = "+ countTriplets(head, x));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript implementation to count triplets
// in a sorted doubly linked list
// whose product is equal to a given value 'x'
// structure of node of doubly linked list
class Node
{
constructor()
{
let data;
let next, prev;
}
}
// function to count pairs whose product
// equal to given 'value'
function countPairs(first,second,value)
{
let count = 0;
// The loop terminates when either of two pointers
// become null, or they cross each other (second.next
// == first), or they become same (first == second)
while (first != null && second != null &&
first != second && second.next != first)
{
// pair found
if ((first.data * second.data) == value)
{
// increment count
count++;
// move first in forward direction
first = first.next;
// move second in backward direction
second = second.prev;
}
// if product is greater than 'value'
// move second in backward direction
else if ((first.data * second.data) > value)
second = second.prev;
// else move first in forward direction
else
first = first.next;
}
// required count of pairs
return count;
}
// function to count triplets in
// a sorted doubly linked list
// whose product is equal to a given value 'x'
function countTriplets(head,x)
{
// if list is empty
if (head == null)
return 0;
let current, first, last;
let count = 0;
// get pointer to the last node of
// the doubly linked list
last = head;
while (last.next != null)
last = last.next;
// traversing the doubly linked list
for (current = head; current != null;
current = current.next)
{
// for each current node
first = current.next;
// count pairs with product(x / current.data)
// in the range first to last and
// add it to the 'count' of triplets
count += countPairs(first, last, x / current.data);
}
// required count of triplets
return count;
}
// A utility function to insert a new node at the
// beginning of doubly linked list
function insert(head,data)
{
// allocate node
let temp = new Node();
// put in the data
temp.data = data;
temp.next = temp.prev = null;
if ((head) == null)
(head) = temp;
else
{
temp.next = head;
(head).prev = temp;
(head) = temp;
}
return head;
}
// Driver code
// start with an empty doubly linked list
let head = null;
// insert values in sorted order
head = insert(head, 9);
head = insert(head, 8);
head = insert(head, 6);
head = insert(head, 5);
head = insert(head, 4);
head = insert(head, 2);
head = insert(head, 1);
let x = 8;
document.write( "Count = "+ countTriplets(head, x));
// This code is contributed by unknown2108
</script>
Producción:
Count = 1
Complejidad de tiempo: O(n^2)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por VishalBachchas y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA