Dada una array de enteros distintos arr[] . La tarea es encontrar un triplete (un grupo de 3 elementos) que tenga la suma mínima.
Nota: El tamaño de la array siempre es mayor que dos.
Ejemplos:
Input : arr[] = {1, 2, 3, 4, -1, 5, -2}
Output : -2
1 - 1 - 2 = -2
Input : arr[] = {5, 6, 0, 0, 1}
Output : 1
0 + 0 + 1.
Enfoque ingenuo: la idea es generar todos los tripletes posibles en la array y luego comparar la suma de un triplete con otros tripletes, luego encontrar la suma mínima.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to find triplet with minimum sum
#include <bits/stdc++.h>
using namespace std;
// Function to find triplet with minimum sum
int getMinimumSum(int arr[] , int n)
{
int ans = INT_MAX;
// Generate all possible triplets
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
for (int k = j + 1; k < n; k++) {
// Calculate sum of each triplet
// and update minimum
ans = min(ans, arr[i] + arr[j] + arr[k]);
}
}
}
return ans;
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 4, 5, -1, 5, -2 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << getMinimumSum(arr, n) << endl;
return 0;
}
Java
// Java Program to find triplet with minimum sum
class GFG
{
// Function to find triplet with minimum sum
static int getMinimumSum(int arr[] , int n)
{
int ans = Integer.MAX_VALUE;
// Generate all possible triplets
for (int i = 0; i < n - 2; i++)
{
for (int j = i + 1; j < n - 1; j++)
{
for (int k = j + 1; k < n; k++)
{
// Calculate sum of each triplet
// and update minimum
ans = Math.min(ans, arr[i] +
arr[j] + arr[k]);
}
}
}
return ans;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 2, 3, 4, 5, -1, 5, -2 };
int n = arr.length;
System.out.print(getMinimumSum(arr, n) + "\n");
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 Program to find triplet with minimum sum import sys # Function to find triplet with minimum sum def getMinimumSum(arr, n): ans = sys.maxsize; # Generate all possible triplets for i in range(n - 2): for j in range(i + 1, n - 1): for k in range(j + 1, n): # Calculate sum of each triplet # and update minimum ans = min(ans, arr[i] + arr[j] + arr[k]); return ans; # Driver Code if __name__ == '__main__': arr = [ 1, 2, 3, 4, 5, -1, 5, -2 ]; n = len(arr); print(getMinimumSum(arr, n)); # This code is contributed by PrinciRaj1992
C#
// C# Program to find triplet with minimum sum
using System;
class GFG
{
// Function to find triplet with minimum sum
static int getMinimumSum(int []arr, int n)
{
int ans = int.MaxValue;
// Generate all possible triplets
for (int i = 0; i < n - 2; i++)
{
for (int j = i + 1; j < n - 1; j++)
{
for (int k = j + 1; k < n; k++)
{
// Calculate sum of each triplet
// and update minimum
ans = Math.Min(ans, arr[i] +
arr[j] + arr[k]);
}
}
}
return ans;
}
// Driver Code
public static void Main()
{
int []arr = { 1, 2, 3, 4, 5, -1, 5, -2 };
int n = arr.Length;
Console.WriteLine(getMinimumSum(arr, n));
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// JavaScript Program to find
// triplet with minimum sum
// Function to find triplet with minimum sum
function getMinimumSum(arr, n)
{
let ans = Number.MAX_SAFE_INTEGER;
// Generate all possible triplets
for (let i = 0; i < n - 2; i++) {
for (let j = i + 1; j < n - 1; j++)
{
for (let k = j + 1; k < n; k++)
{
// Calculate sum of each triplet
// and update minimum
ans = Math.min(ans, arr[i] +
arr[j] + arr[k]);
}
}
}
return ans;
}
// Driver Code
let arr = [ 1, 2, 3, 4, 5, -1, 5, -2 ];
let n = arr.length;
document.write(getMinimumSum(arr, n) + "<br>");
// This code is contributed by Surbhi Tyagi.
</script>
Producción:
-2
Complejidad de tiempo: 0 (n ^ 3)
Espacio auxiliar: 0 (1)
Enfoque eficiente: la idea es atravesar la array y calcular el elemento mínimo, segundo mínimo y tercero mínimo presente en la array e imprimir la suma de estos tres elementos.
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ Program to find triplet with a minimum sum
#include <bits/stdc++.h>
using namespace std;
// Function to find triplet with minimum sum
int getMinimumSum(int arr[] , int n)
{
// fMin: First minimum
// sMin: Second minimum
// tMin: Third minimum
int fMin = INT_MAX, sMin = INT_MAX, tMin = INT_MAX;
for (int i = 0; i < n; i++) {
// Update the first, second and third minimum
if (arr[i] < fMin) {
tMin = sMin;
sMin = fMin;
fMin = arr[i];
}
// update second and third minimum
else if (arr[i] < sMin) {
tMin = sMin;
sMin = arr[i];
}
else if (arr[i] < tMin) {
tMin = arr[i];
}
}
return (fMin + sMin + tMin);
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 4, 5, -1, 5, -2 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << getMinimumSum(arr, n) << endl;
return 0;
}
Java
// Java Program to find triplet with a minimum sum
class GFG
{
// Function to find triplet with minimum sum
static int getMinimumSum(int arr[] , int n)
{
// fMin: First minimum
// sMin: Second minimum
// tMin: Third minimum
int fMin = Integer.MAX_VALUE,
sMin = Integer.MAX_VALUE,
tMin = Integer.MAX_VALUE;
for (int i = 0; i < n; i++)
{
// Update the first, second and third minimum
if (arr[i] < fMin)
{
tMin = sMin;
sMin = fMin;
fMin = arr[i];
}
// update second and third minimum
else if (arr[i] < sMin)
{
tMin = sMin;
sMin = arr[i];
}
else if (arr[i] < tMin)
{
tMin = arr[i];
}
}
return (fMin + sMin + tMin);
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 2, 3, 4, 5, -1, 5, -2 };
int n = arr.length;
System.out.print(getMinimumSum(arr, n) +"\n");
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 Program to find triplet with a minimum sum import sys # Function to find triplet with minimum sum def getMinimumSum(arr, n): # fMin: First minimum # sMin: Second minimum # tMin: Third minimum fMin = sys.maxsize; sMin = sys.maxsize; tMin = sys.maxsize; for i in range(n): # Update the first, second and third minimum if (arr[i] < fMin): tMin = sMin; sMin = fMin; fMin = arr[i]; # update second and third minimum elif(arr[i] < sMin): tMin = sMin; sMin = arr[i]; elif(arr[i] < tMin): tMin = arr[i]; return (fMin + sMin + tMin); # Driver Code if __name__ == '__main__': arr = [ 1, 2, 3, 4, 5, -1, 5, -2]; n = len(arr); print(getMinimumSum(arr, n)); # This code is contributed by 29AjayKumar
C#
// C# Program to find triplet with a minimum sum
using System;
class GFG
{
// Function to find triplet with minimum sum
static int getMinimumSum(int []arr, int n)
{
// fMin: First minimum
// sMin: Second minimum
// tMin: Third minimum
int fMin = int.MaxValue,
sMin = int.MaxValue,
tMin = int.MaxValue;
for (int i = 0; i < n; i++)
{
// Update the first, second and third minimum
if (arr[i] < fMin)
{
tMin = sMin;
sMin = fMin;
fMin = arr[i];
}
// update second and third minimum
else if (arr[i] < sMin)
{
tMin = sMin;
sMin = arr[i];
}
else if (arr[i] < tMin)
{
tMin = arr[i];
}
}
return (fMin + sMin + tMin);
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 1, 2, 3, 4, 5, -1, 5, -2 };
int n = arr.Length;
Console.Write(getMinimumSum(arr, n) +"\n");
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript Program to find triplet
// with a minimum sum
// Function to find triplet with minimum sum
function getMinimumSum(arr , n)
{
// fMin: First minimum
// sMin: Second minimum
// tMin: Third minimum
var fMin = 1000000000, sMin = 1000000000,
tMin = 1000000000;
for (var i = 0; i < n; i++) {
// Update the first, second and third minimum
if (arr[i] < fMin) {
tMin = sMin;
sMin = fMin;
fMin = arr[i];
}
// update second and third minimum
else if (arr[i] < sMin) {
tMin = sMin;
sMin = arr[i];
}
else if (arr[i] < tMin) {
tMin = arr[i];
}
}
return (fMin + sMin + tMin);
}
// Driver Code
var arr = [1, 2, 3, 4, 5, -1, 5, -2];
var n = arr.length;
document.write( getMinimumSum(arr, n));
</script>
Producción:
-2
Complejidad de tiempo: 0(n)
Espacio auxiliar: 0(1)