Dada una array arr[] de N enteros y un entero X , la tarea es encontrar tres enteros en arr[] tales que la suma sea la más cercana a X.
Ejemplos:
Input: arr[] = {-1, 2, 1, -4}, X = 1
Output: 2
Explanation:
Sums of triplets:
(-1) + 2 + 1 = 2
(-1) + 2 + (-4) = -3
2 + 1 + (-4) = -1
2 is closest to 1.
Input: arr[] = {1, 2, 3, 4, -5}, X = 10
Output: 9
Explanation:
Sums of triplets:
1 + 2 + 3 = 6
2 + 3 + 4 = 9
1 + 3 + 4 = 7
...
9 is closest to 10.
Enfoque simple: el enfoque ingenuo es explorar todos los subconjuntos de tamaño 3 y realizar un seguimiento de la diferencia entre X y la suma de este subconjunto. Luego devuelve el subconjunto cuya diferencia entre su suma y X es mínima.
Algoritmo:
- Cree tres bucles anidados con los contadores i, j y k respectivamente.
- El primer ciclo comenzará de principio a fin, el segundo ciclo se ejecutará desde i+1 hasta el final, el tercer ciclo se ejecutará desde j+1 hasta el final.
- Compruebe si la diferencia de la suma de los elementos i-ésimo, j-ésimo y k-ésimo con la suma dada es menor que el mínimo actual o no. Actualizar el mínimo actual
- Imprime la suma más cercana.
Implementación:
C++14
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the sum of a
// triplet which is closest to x
int solution(vector<int>& arr, int x)
{
// To store the closest sum
int closestSum = INT_MAX;
// Run three nested loops each loop
// for each element of triplet
for (int i = 0; i < arr.size() ; i++)
{
for(int j =i + 1; j < arr.size(); j++)
{
for(int k =j + 1; k < arr.size(); k++)
{
//update the closestSum
if(abs(x - closestSum) > abs(x - (arr[i] + arr[j] + arr[k])))
closestSum = (arr[i] + arr[j] + arr[k]);
}
}
}
// Return the closest sum found
return closestSum;
}
// Driver code
int main()
{
vector<int> arr = { -1, 2, 1, -4 };
int x = 1;
cout << solution(arr, x);
return 0;
}
Java
// Java implementation of the above approach
class GFG{
// Function to return the sum of a
// triplet which is closest to x
public static int solution(int arr[], int x)
{
// To store the closest sum
int closestSum = Integer.MAX_VALUE;
// Run three nested loops each loop
// for each element of triplet
for(int i = 0; i < arr.length ; i++)
{
for(int j = i + 1; j < arr.length; j++)
{
for(int k = j + 1; k < arr.length; k++)
{
// Update the closestSum
if (Math.abs(x - closestSum) >
Math.abs(x - (arr[i] + arr[j] + arr[k])))
closestSum = (arr[i] + arr[j] + arr[k]);
}
}
}
// Return the closest sum found
return closestSum;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { -1, 2, 1, -4 };
int x = 1;
System.out.print(solution(arr, x));
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python3 implementation of the above approach import sys # Function to return the sum of a # triplet which is closest to x def solution(arr, x): # To store the closest sum closestSum = sys.maxsize # Run three nested loops each loop # for each element of triplet for i in range (len(arr)) : for j in range(i + 1, len(arr)): for k in range(j + 1, len( arr)): # Update the closestSum if(abs(x - closestSum) > abs(x - (arr[i] + arr[j] + arr[k]))): closestSum = (arr[i] + arr[j] + arr[k]) # Return the closest sum found return closestSum # Driver code if __name__ == "__main__": arr = [ -1, 2, 1, -4 ] x = 1 print(solution(arr, x)) # This code is contributed by chitranayal
C#
// C# implementation of the above approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG{
// Function to return the sum of a
// triplet which is closest to x
static int solution(ArrayList arr, int x)
{
// To store the closest sum
int closestSum = int.MaxValue;
// Run three nested loops each loop
// for each element of triplet
for(int i = 0; i < arr.Count; i++)
{
for(int j = i + 1; j < arr.Count; j++)
{
for(int k = j + 1; k < arr.Count; k++)
{
if (Math.Abs(x - closestSum) >
Math.Abs(x - ((int)arr[i] +
(int)arr[j] + (int)arr[k])))
{
closestSum = ((int)arr[i] +
(int)arr[j] +
(int)arr[k]);
}
}
}
}
// Return the closest sum found
return closestSum;
}
// Driver code
public static void Main(string[] args)
{
ArrayList arr = new ArrayList(){ -1, 2, 1, -4 };
int x = 1;
Console.Write(solution(arr, x));
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// Javascript implementation of the approach
// Function to return the sum of a
// triplet which is closest to x
function solution(arr, x)
{
// To store the closest sum
let closestSum = Number.MAX_VALUE;
// Run three nested loops each loop
// for each element of triplet
for(let i = 0; i < arr.length ; i++)
{
for(let j =i + 1; j < arr.length; j++)
{
for(let k =j + 1; k < arr.length; k++)
{
// Update the closestSum
if (Math.abs(x - closestSum) >
Math.abs(x - (arr[i] + arr[j] + arr[k])))
closestSum = (arr[i] + arr[j] + arr[k]);
}
}
}
// Return the closest sum found
return closestSum;
}
// Driver code
let arr = [ -1, 2, 1, -4 ];
let x = 1;
document.write(solution(arr, x));
// This code is contributed by rishavmahato348
</script>
Producción:
2
Análisis de Complejidad:
- Complejidad temporal: O(N 3 ).
Tres bucles anidados atraviesan la array, por lo que la complejidad del tiempo es O (n ^ 3). - Complejidad espacial : O(1).
Como no se requiere espacio adicional.
Enfoque eficiente: al ordenar la array, se puede mejorar la eficiencia del algoritmo. Este enfoque eficiente utiliza la técnica de dos puntos . Atraviese la array y fije el primer elemento del triplete. Ahora use el algoritmo Two Pointers para encontrar el número más cercano a x – array[i] . Actualiza la suma más cercana. El algoritmo de dos punteros toma un tiempo lineal, por lo que es mejor que un bucle anidado.
Algoritmo:
- Ordenar la array dada.
- Recorra la array y fije el primer elemento del posible triplete, arr[i].
- Luego fije dos punteros , uno en I + 1 y el otro en n – 1 . Y mira la suma,
- Si la suma es más pequeña que la suma a la que necesitamos llegar, aumentamos el primer puntero.
- De lo contrario, si la suma es mayor, disminuya el puntero final para reducir la suma.
- Actualice la suma más cercana encontrada hasta el momento.
Implementación:
C++14
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the sum of a
// triplet which is closest to x
int solution(vector<int>& arr, int x)
{
// Sort the array
sort(arr.begin(), arr.end());
// To store the closest sum
//not using INT_MAX to avoid overflowing condition
int closestSum = 1000000000;
// Fix the smallest number among
// the three integers
for (int i = 0; i < arr.size() - 2; i++) {
// Two pointers initially pointing at
// the last and the element
// next to the fixed element
int ptr1 = i + 1, ptr2 = arr.size() - 1;
// While there could be more pairs to check
while (ptr1 < ptr2) {
// Calculate the sum of the current triplet
int sum = arr[i] + arr[ptr1] + arr[ptr2];
// if sum is equal to x, return sum as
if (sum == x)
return sum;
// If the sum is more closer than
// the current closest sum
if (abs(x - sum) < abs(x - closestSum)) {
closestSum = sum;
}
// If sum is greater then x then decrement
// the second pointer to get a smaller sum
if (sum > x) {
ptr2--;
}
// Else increment the first pointer
// to get a larger sum
else {
ptr1++;
}
}
}
// Return the closest sum found
return closestSum;
}
// Driver code
int main()
{
vector<int> arr = { -1, 2, 1, -4 };
int x = 1;
cout << solution(arr, x);
return 0;
}
Java
// Java implementation of the above approach
import static java.lang.Math.abs;
import java.util.*;
class GFG
{
// Function to return the sum of a
// triplet which is closest to x
static int solution(Vector<Integer> arr, int x)
{
// Sort the array
Collections.sort(arr);
// To store the closest sum
// Assigning long to avoid overflow condition
// when array has negative integers
long closestSum = Integer.MAX_VALUE;
// Fix the smallest number among
// the three integers
for (int i = 0; i < arr.size() - 2; i++)
{
// Two pointers initially pointing at
// the last and the element
// next to the fixed element
int ptr1 = i + 1, ptr2 = arr.size() - 1;
// While there could be more pairs to check
while (ptr1 < ptr2)
{
// Calculate the sum of the current triplet
int sum = arr.get(i) + arr.get(ptr1) + arr.get(ptr2);
// If the sum is more closer than
// the current closest sum
if (abs(x - sum) < abs(x - closestSum))
{
closestSum = sum;
}
// If sum is greater then x then decrement
// the second pointer to get a smaller sum
if (sum > x)
{
ptr2--;
}
// Else increment the first pointer
// to get a larger sum
else
{
ptr1++;
}
}
}
// Return the closest sum found
return (int)closestSum;
}
// Driver code
public static void main(String[] args)
{
Vector arr = new Vector(Arrays.asList( -1, 2, 1, -4 ));
int x = 1;
System.out.println(solution(arr, x));
}
}
/* This code is contributed by PrinciRaj1992 */
Python3
# Python3 implementation of the approach import sys # Function to return the sum of a # triplet which is closest to x def solution(arr, x) : # Sort the array arr.sort(); # To store the closest sum closestSum = sys.maxsize; # Fix the smallest number among # the three integers for i in range(len(arr)-2) : # Two pointers initially pointing at # the last and the element # next to the fixed element ptr1 = i + 1; ptr2 = len(arr) - 1; # While there could be more pairs to check while (ptr1 < ptr2) : # Calculate the sum of the current triplet sum = arr[i] + arr[ptr1] + arr[ptr2]; # If the sum is more closer than # the current closest sum if (abs(x - sum) < abs(x - closestSum)) : closestSum = sum; # If sum is greater then x then decrement # the second pointer to get a smaller sum if (sum > x) : ptr2 -= 1; # Else increment the first pointer # to get a larger sum else : ptr1 += 1; # Return the closest sum found return closestSum; # Driver code if __name__ == "__main__" : arr = [ -1, 2, 1, -4 ]; x = 1; print(solution(arr, x)); # This code is contributed by AnkitRai01
C#
// C# implementation of the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to return the sum of a
// triplet which is closest to x
static int solution(List<int> arr, int x)
{
// Sort the array
arr.Sort();
// To store the closest sum
int closestSum = int.MaxValue;
// Fix the smallest number among
// the three integers
for (int i = 0; i < arr.Count - 2; i++)
{
// Two pointers initially pointing at
// the last and the element
// next to the fixed element
int ptr1 = i + 1, ptr2 = arr.Count - 1;
// While there could be more pairs to check
while (ptr1 < ptr2)
{
// Calculate the sum of the current triplet
int sum = arr[i] + arr[ptr1] + arr[ptr2];
// If the sum is more closer than
// the current closest sum
if (Math.Abs(x - sum) <
Math.Abs(x - closestSum))
{
closestSum = sum;
}
// If sum is greater then x then decrement
// the second pointer to get a smaller sum
if (sum > x)
{
ptr2--;
}
// Else increment the first pointer
// to get a larger sum
else
{
ptr1++;
}
}
}
// Return the closest sum found
return closestSum;
}
// Driver code
public static void Main(String[] args)
{
int []ar = { -1, 2, 1, -4 };
List<int> arr = new List<int>(ar);
int x = 1;
Console.WriteLine(solution(arr, x));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// JavaScript implementation of the approach
// Function to return the sum of a
// triplet which is closest to x
function solution(arr, x)
{
// Sort the array
arr.sort((a, b) => a - b);
// To store the closest sum
// not using INT_MAX to avoid
// overflowing condition
let closestSum = 1000000000;
// Fix the smallest number among
// the three integers
for (let i = 0; i < arr.length - 2; i++)
{
// Two pointers initially pointing at
// the last and the element
// next to the fixed element
let ptr1 = i + 1, ptr2 = arr.length - 1;
// While there could be more pairs to check
while (ptr1 < ptr2) {
// Calculate the sum of the current triplet
let sum = arr[i] + arr[ptr1] + arr[ptr2];
// If the sum is more closer than
// the current closest sum
if (Math.abs(1*x - sum) < Math.abs(1*x - closestSum))
{
closestSum = sum;
}
// If sum is greater then x then decrement
// the second pointer to get a smaller sum
if (sum > x) {
ptr2--;
}
// Else increment the first pointer
// to get a larger sum
else {
ptr1++;
}
}
}
// Return the closest sum found
return closestSum;
}
// Driver code
let arr = [ -1, 2, 1, -4 ];
let x = 1;
document.write(solution(arr, x));
// This code is contributed by Surbhi Tyagi.
</script>
Producción:
2
Análisis de Complejidad:
- Complejidad temporal: O(N 2 ) .
Solo hay dos bucles anidados que atraviesan la array, por lo que la complejidad del tiempo es O (n ^ 2). El algoritmo de dos punteros toma el tiempo O (n) y el primer elemento se puede arreglar usando otro recorrido anidado. - Complejidad espacial : O(1) .
Como no se requiere espacio adicional.
Publicación traducida automáticamente
Artículo escrito por Ripunjoy Medhi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA