Dada una lista ordenada doblemente enlazada de N Nodes y un número entero X , la tarea es encontrar la suma de tres Nodes en la lista que está más cerca de X .
Ejemplos:
Entrada: DLL: -8 ↔ 2 ↔ 3 ↔ 4 ↔ 5, X = 1
Salida: 1
Explicación: Los tres enteros necesarios {-8, 4, 5} cuya suma es 1 y está más cerca de 1.Entrada: DLL: 1 ↔ 2 ↔ 3 ↔ 4, X = 3
Salida: 6
Explicación: Los tres enteros requeridos son {1, 2, 3} cuya suma es 6 y está más cerca de X = 3.
Enfoque ingenuo : el enfoque más simple para resolver el problema dado es generar todos los tripletes posibles utilizando tres bucles anidados y luego elegir el triplete que tiene la suma más cercana a X e imprimir la suma del triplete.
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(1)
Enfoque eficiente: Para optimizar el enfoque anterior, la idea es utilizar la técnica de 3 punteros . Siga los pasos a continuación para resolver este problema:
- Inicialice 4 variables, la primera y la segunda apuntando al Node principal de la lista doblemente enlazada, es decir, primera = cabeza , segunda = cabeza y cola y la tercera , ambas inicializadas en el último Node de la lista doblemente enlazada .
- Inicialice una variable diff , inicializada como INT_MAX , que almacena la suma más cercana a X .
- Iterar mientras el primer Node no es NULL y realizar los siguientes pasos:
- Inicialice el segundo al siguiente del primero , es decir, segundo = primero→siguiente y tercero = cola (el último Node de la lista doblemente enlazada).
- Iterar mientras el segundo y el tercero no son NULL y el tercero no es igual al segundo .
- Inicialice una variable, digamos, sume como (primero→datos + segundo→datos + tercero→datos) .
- Si el valor absoluto de X – sum es menor que el valor absoluto de X – diff , actualice el valor de diff como sum.
- Si sum es menor que X , entonces incremente el segundo puntero, es decir, second = second→next .
- De lo contrario, decremente tercero , es decir, tercero = tercero→anterior.
- Mueva el primer puntero al siguiente puntero, es decir, primero = primero→siguiente .
- Después de completar los pasos anteriores, imprima el valor de diff como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Doubly linked list node
struct Node {
int data;
struct Node *next, *prev;
};
// 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();
// Fill the data value in it
temp->data = data;
temp->next = temp->prev = NULL;
// If head is NULL change
// head to temp
if ((*head) == NULL) {
(*head) = temp;
}
// Insert the node before head
else {
temp->next = *head;
(*head)->prev = temp;
(*head) = temp;
}
}
// Function to find sum of triplet
// closest to X
void closestTripletSum(struct Node* head, int X)
{
// Points to the first node
// of the triplet
struct Node* first = head;
// Points to the second node
// of the triplet
struct Node* second = head->next;
// Stores the last node of
// doubly linked list
struct Node* tail = head;
// Traverse till end of the list
while (tail->next != NULL) {
tail = tail->next;
}
// Stores the sum closest to X
int diff = INT_MAX;
// Points to the third node
// of the triplet
struct Node* third = tail;
// Iterate till the end of the list
while (first != NULL) {
second = first->next;
third = tail;
while (second != NULL && third != NULL
&& third != second) {
int sum = (first->data + second->data
+ third->data);
// Check if the current sum
// is closest to X
if (abs(X - sum) < abs(X - diff)) {
// Update the value of diff
diff = sum;
}
// Check if sum is less than X
if (sum < X) {
// Increment the second
// pointer
second = second->next;
}
else {
// Decrement the third
// pointer
third = third->prev;
}
}
// Move the first pointer
// ahead
first = first->next;
}
// Print the closest sum
cout << diff;
}
// Driver Code
int main()
{
// Given Input
struct Node* head = NULL;
insert(&head, 4);
insert(&head, 3);
insert(&head, 2);
insert(&head, 1);
int X = 3;
// Function Call
closestTripletSum(head, X);
return 0;
}
Java
// Java program for the above approach
class GFG {
// Doubly linked list node
static class Node {
int data;
Node next, prev;
};
static Node head;
// Function to insert a new node at
// the beginning of doubly linked
// list
static void insert(int data)
{
// Allocate node
Node temp = new Node();
// Fill the data value in it
temp.data = data;
temp.next = temp.prev = null;
// If head is null change
// head to temp
if ((head) == null) {
(head) = temp;
}
// Insert the node before head
else {
temp.next = head;
(head).prev = temp;
(head) = temp;
}
}
// Function to find sum of triplet
// closest to X
static void closestTripletSum(int X)
{
// Points to the first node
// of the triplet
Node first = head;
// Points to the second node
// of the triplet
Node second = head.next;
// Stores the last node of
// doubly linked list
Node tail = head;
// Traverse till end of the list
while (tail.next != null) {
tail = tail.next;
}
// Stores the sum closest to X
int diff = Integer.MAX_VALUE;
// Points to the third node
// of the triplet
Node third = tail;
// Iterate till the end of the list
while (first != null) {
second = first.next;
third = tail;
while (second != null && third != null
&& third != second) {
int sum = (first.data + second.data
+ third.data);
// Check if the current sum
// is closest to X
if (Math.abs(X - sum)
< Math.abs(X - diff)) {
// Update the value of diff
diff = sum;
}
// Check if sum is less than X
if (sum < X) {
// Increment the second
// pointer
second = second.next;
}
else {
// Decrement the third
// pointer
third = third.prev;
}
}
// Move the first pointer
// ahead
first = first.next;
}
// Print the closest sum
System.out.print(diff);
}
// Driver Code
public static void main(String[] args)
{
// Given Input
head = null;
insert(4);
insert(3);
insert(2);
insert(1);
int X = 3;
// Function Call
closestTripletSum(X);
}
}
// This code is contributed by umadevi9616
Python3
# Python program for the above approach import sys # Doubly linked list Node class Node: def __init__(self): self.data = 0; self.next = None; self.prev = None; head = None; # Function to insert a new Node at # the beginning of doubly linked # list def insert(data): # Allocate Node temp = Node(); # Fill the data value in it temp.data = data; temp.next = temp.prev = None; # If head is None change # head to temp global head; if ((head) == None): (head) = temp; # Insert the Node before head else: temp.next = head; (head).prev = temp; (head) = temp; # Function to find sum of triplet # closest to X def closestTripletSum(X): # Points to the first Node # of the triplet first = head; # Points to the second Node # of the triplet second = head.next; # Stores the last Node of # doubly linked list tail = head; # Traverse till end of the list while (tail.next != None): tail = tail.next; # Stores the sum closest to X diff = sys.maxsize; # Points to the third Node # of the triplet third = tail; # Iterate till the end of the list while (first != None): second = first.next; third = tail; while (second != None and third != None and third != second): sum = (first.data + second.data + third.data); # Check if the current sum # is closest to X if (abs(X - sum) < abs(X - diff)): # Update the value of diff diff = sum; # Check if sum is less than X if (sum < X): # Increment the second # pointer second = second.next; else: # Decrement the third # pointer third = third.prev; # Move the first pointer # ahead first = first.next; # Print the closest sum print(diff); # Driver Code if __name__ == '__main__': # Given Input head = None; insert(4); insert(3); insert(2); insert(1); X = 3; # Function Call closestTripletSum(X); # This code is contributed by umadevi9616
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG {
// Doubly linked list node
public class Node {
public int data;
public Node next, prev;
};
static Node head;
// Function to insert a new node at
// the beginning of doubly linked
// list
static void insert(int data) {
// Allocate node
Node temp = new Node();
// Fill the data value in it
temp.data = data;
temp.next = temp.prev = null;
// If head is null change
// head to temp
if ((head) == null) {
(head) = temp;
}
// Insert the node before head
else {
temp.next = head;
(head).prev = temp;
(head) = temp;
}
}
// Function to find sum of triplet
// closest to X
static void closestTripletSum(int X) {
// Points to the first node
// of the triplet
Node first = head;
// Points to the second node
// of the triplet
Node second = head.next;
// Stores the last node of
// doubly linked list
Node tail = head;
// Traverse till end of the list
while (tail.next != null) {
tail = tail.next;
}
// Stores the sum closest to X
int diff = int.MaxValue;
// Points to the third node
// of the triplet
Node third = tail;
// Iterate till the end of the list
while (first != null) {
second = first.next;
third = tail;
while (second != null && third != null && third != second) {
int sum = (first.data + second.data + third.data);
// Check if the current sum
// is closest to X
if (Math.Abs(X - sum) < Math.Abs(X - diff)) {
// Update the value of diff
diff = sum;
}
// Check if sum is less than X
if (sum < X) {
// Increment the second
// pointer
second = second.next;
} else {
// Decrement the third
// pointer
third = third.prev;
}
}
// Move the first pointer
// ahead
first = first.next;
}
// Print the closest sum
Console.Write(diff);
}
// Driver Code
public static void Main(String[] args) {
// Given Input
head = null;
insert(4);
insert(3);
insert(2);
insert(1);
int X = 3;
// Function Call
closestTripletSum(X);
}
}
// This code is contributed by umadevi9616
Javascript
<script>
// javascript program for the above approach // Doubly linked list node
class Node {
constructor(val = 0) {
this.data = val;
this.prev = null;
this.next = null;
}
}
var head;
// Function to insert a new node at
// the beginning of doubly linked
// list
function insert(data) {
// Allocate node
var temp = new Node();
// Fill the data value in it
temp.data = data;
temp.next = temp.prev = null;
// If head is null change
// head to temp
if ((head) == null) {
(head) = temp;
}
// Insert the node before head
else {
temp.next = head;
(head).prev = temp;
(head) = temp;
}
}
// Function to find sum of triplet
// closest to X
function closestTripletSum(X)
{
// Points to the first node
// of the triplet
var first = head;
// Points to the second node
// of the triplet
var second = head.next;
// Stores the last node of
// doubly linked list
var tail = head;
// Traverse till end of the list
while (tail.next != null) {
tail = tail.next;
}
// Stores the sum closest to X
var diff = Number.MAX_VALUE;
// Points to the third node
// of the triplet
var third = tail;
// Iterate till the end of the list
while (first != null) {
second = first.next;
third = tail;
while (second != null && third != null && third != second) {
var sum = (first.data + second.data + third.data);
// Check if the current sum
// is closest to X
if (Math.abs(X - sum) < Math.abs(X - diff)) {
// Update the value of diff
diff = sum;
}
// Check if sum is less than X
if (sum < X) {
// Increment the second
// pointer
second = second.next;
} else {
// Decrement the third
// pointer
third = third.prev;
}
}
// Move the first pointer
// ahead
first = first.next;
}
// Print the closest sum
document.write(diff);
}
// Driver Code
// Given Input
head = null;
insert(4);
insert(3);
insert(2);
insert(1);
var X = 3;
// Function Call
closestTripletSum(X);
// This code is contributed by umadevi9616
</script>
Producción
6
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)