Dada una lista ordenada doblemente enlazada de Nodes distintos (no hay dos Nodes que tengan los mismos datos) y un valor x . Cuente los tripletes en la lista que suman un valor x dado .
Ejemplos:
Método 1 (enfoque ingenuo):
el uso de tres bucles anidados genera todos los tripletes y verifica si los elementos en el triplete suman x o no.
C++
// C++ implementation to count triplets in a sorted doubly linked list
// whose sum 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 sum 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 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
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 = 17;
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.io.*;
import java.util.*;
// Represents node of a doubly linked list
class Node
{
int data;
Node prev, next;
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 = 17;
System.out.println("count = " + countTriplets(head, x));
}
}
// This code is contributed by rachana soma
Python3
# Python3 implementation to count triplets # in a sorted doubly linked list # whose sum is equal to a given value 'x' # structure of node of doubly linked list class Node: def __init__(self): self.data = None 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 = head ptr2 = None ptr3 = None count = 0 # generate all possible triplets while (ptr1 != None ): ptr2 = ptr1.next while ( ptr2 != None ): ptr3 = ptr2.next while ( ptr3 != None ): # if elements in the current triplet sum up to 'x' if ((ptr1.data + ptr2.data + ptr3.data) == x): # increment count 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, data): # allocate node temp = Node() # 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 # 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 = 17 print( "Count = ", countTriplets(head, x)) # This code is contributed by Arnab Kundu
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 = 17;
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 = 17;
document.write("count = " + countTriplets(head, x));
// This code is contributed by umadevi9616
</script>
Producción:
Count = 2
Tiempo Complejidad: 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_sum (suma de datos en los dos Nodes) y verifique si (x-p_sum) existe en la tabla hash o no. Si existe, también verifique que los dos Nodes en el par no sean iguales al Node asociado con (x-p_sum) en la tabla hash y finalmente incremente el conteo . Regresar (contar/3) ya que cada triplete se cuenta 3 veces en el proceso anterior.
C++
// C++ implementation to count triplets in a sorted doubly linked list
// whose sum 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 sum 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_sum - sum of elements in the current pair
int p_sum = ptr1->data + ptr2->data;
// if 'x-p_sum' is present in 'um' and either of the two nodes
// are not equal to the 'um[x-p_sum]' node
if (um.find(x - p_sum) != um.end() && um[x - p_sum] != ptr1
&& um[x - p_sum] != 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
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 = 17;
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.*;
class GFG{
// structure of node of doubly linked list
static class Node {
int data;
Node next, prev;
Node(int val)
{
data = val;
prev = null;
next = null;
}
};
// 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 ptr, ptr1, ptr2;
int count = 0;
// unordered_map 'um' implemented as hash table
HashMap<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_sum - sum of elements in the current pair
int p_sum = ptr1.data + ptr2.data;
// if 'x-p_sum' is present in 'um' and either of the two nodes
// are not equal to the 'um[x-p_sum]' node
if (um.containsKey(x - p_sum) && um.get(x - p_sum) != ptr1
&& um.get(x - p_sum) != 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 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 program to test above
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 = 17;
System.out.print("Count = "
+ countTriplets(head, x));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation to count triplets in a sorted doubly linked list
# whose sum 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 triplets in a sorted doubly linked list
# whose sum is equal to a given value 'x'
def countTriplets(head, x):
ptr2=head
count = 0;
# unordered_map 'um' implemented as hash table
um = dict()
ptr = head
# insert the <node data, node pointer> tuple in 'um'
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_sum - sum of elements in the current pair
p_sum = ptr1.data + ptr2.data;
# if 'x-p_sum' is present in 'um' and either of the two nodes
# are not equal to the 'um[x-p_sum]' node
if ((x-p_sum) in um) and um[x - p_sum] != ptr1 and um[x - p_sum] != 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);
if ((head) == None):
(head) = temp;
else:
temp.next = head;
(head).prev = temp;
(head) = temp;
return head
# Driver program to test above
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 = 17;
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 sum is equal to a given value 'x'
using System;
using System.Collections.Generic;
class GFG
{
// structure of node of doubly linked list
class Node {
public int data;
public Node next, prev;
public Node(int val)
{
data = val;
prev = null;
next = null;
}
};
// 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 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)
if(um.ContainsKey(ptr.data))
um[ptr.data] = ptr;
else
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_sum - sum of elements in the current pair
int p_sum = ptr1.data + ptr2.data;
// if 'x-p_sum' is present in 'um' and either of the two nodes
// are not equal to the 'um[x-p_sum]' node
if (um.ContainsKey(x - p_sum) && um[x - p_sum] != ptr1
&& um[x - p_sum] != 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 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 = 17;
Console.Write("Count = "
+ countTriplets(head, x));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript implementation to count
// triplets in a sorted doubly linked list
// whose sum is equal to a given value 'x'
// Structure of node of doubly linked list
class Node{
constructor(data)
{
this.data = data;
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)
{
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_sum - sum of elements in
// the current pair
let p_sum = ptr1.data + ptr2.data;
// If 'x-p_sum' is present in 'um'
// and either of the two nodes are
// not equal to the 'um[x-p_sum]' node
if (um.has(x - p_sum) &&
um.get(x - p_sum) != ptr1 &&
um.get(x - p_sum) != 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, val)
{
// Allocate node
let 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
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 = 17;
document.write("Count = " +
countTriplets(head, x));
// This code is contributed by patel2127
</script>
Producción:
Count = 2
Complejidad de Tiempo: O(n 2 )
Espacio Auxiliar: O(n)
Método 3 Enfoque eficiente (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 primer hasta el último puntero que suman 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.
C++
// C++ implementation to count triplets in a sorted doubly linked list
// whose sum 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 sum 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 sum 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 sum 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 sum(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 = 17;
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.*;
class GFG{
// structure of node of doubly linked list
static class Node {
int data;
Node next, prev;
};
// function to count pairs whose sum 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 sum 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 sum 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 sum(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 program to test above
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 = 17;
System.out.print("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'
# 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 pairs whose sum
# 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 sum 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 sum is equal
# to a given value 'x'
def countTriplets(head, x):
# If list is empty
if (head == None):
return 0
current, first, last = head, None, None
count = 0
# Get pointer to the last node of
# the doubly linked list
last = head
while (last.next != None):
last = last.next
# Traversing the doubly linked list
while current != None:
# For each current node
first = current.next
# count pairs with sum(x - current.data) in
# the range first to last and add it to the
# 'count' of triplets
count, current = count + countPairs(
first, last, x - current.data), 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.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 = 17
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 sum 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 sum 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 sum 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 sum 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 sum(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 program to test above
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 = 17;
Console.Write("Count = "
+ countTriplets(head, x));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation to count
// triplets in a sorted doubly linked list
// whose sum is equal to a given value 'x'
// Structure of node of doubly linked list
class Node
{
constructor(data)
{
this.data = data;
this.next = this.prev = null;
}
}
// Function to count pairs whose sum
// 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 sum 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 sum 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 sum(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 = 17;
document.write("Count = " +
countTriplets(head, x));
// This code is contributed by unknown2108
</script>
Producción:
Count = 2
Tiempo Complejidad: O(n 2 )
Espacio Auxiliar: O(1)
Este artículo es una contribución de Ayush Jauhari . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA