Dado un conjunto S (todos los elementos distintos) de enteros, encuentre el mayor d tal que a + b + c = d
donde a, b, c y d son elementos distintos de S.
Constraints: 1 ≤ number of elements in the set ≤ 1000 INT_MIN ≤ each element in the set ≤ INT_MAX
Ejemplos:
Entrada: S[] = {2, 3, 5, 7, 12}
Salida: 12
Explicación: 12 es la d más grande que se puede representar como 12 = 2 + 3 + 7
Entrada: S[] = {2, 16, 64, 256, 1024}
Salida: Sin solución
Método 1 (Fuerza bruta)
Podemos resolver este problema usando un enfoque simple de fuerza bruta que no es muy eficiente como |S| puede ser tan grande como 1000. Ordenaremos el conjunto de elementos y comenzaremos por encontrar el d más grande equiparándolo con la suma de todas las combinaciones posibles de a, b y c.
A continuación se muestra la implementación de la idea anterior:
C++
// CPP Program to find the largest d
// such that d = a + b + c
#include <bits/stdc++.h>
using namespace std;
int findLargestd(int S[], int n)
{
bool found = false;
// sort the array in
// ascending order
sort(S, S + n);
// iterating from backwards to
// find the required largest d
for (int i = n - 1; i >= 0; i--)
{
for (int j = 0; j < n; j++)
{
// since all four a, b, c,
// d should be distinct
if (i == j)
continue;
for (int k = j + 1; k < n; k++)
{
if (i == k)
continue;
for (int l = k + 1; l < n; l++)
{
if (i == l)
continue;
// if the current combination
// of j, k, l in the set is
// equal to S[i] return this
// value as this would be the
// largest d since we are
// iterating in descending order
if (S[i] == S[j] + S[k] + S[l])
{
found = true;
return S[i];
}
}
}
}
}
if (found == false)
return INT_MIN;
}
// Driver Code
int main()
{
// Set of distinct Integers
int S[] = { 2, 3, 5, 7, 12 };
int n = sizeof(S) / sizeof(S[0]);
int ans = findLargestd(S, n);
if (ans == INT_MIN)
cout << "No Solution" << endl;
else
cout << "Largest d such that a + b + "
<< "c = d is " << ans << endl;
return 0;
}
Java
// Java Program to find the largest
// such that d = a + b + c
import java.io.*;
import java.util.Arrays;
class GFG
{
// function to find largest d
static int findLargestd(int []S, int n)
{
boolean found = false;
// sort the array in
// ascending order
Arrays.sort(S);
// iterating from backwards to
// find the required largest d
for (int i = n - 1; i >= 0; i--)
{
for (int j = 0; j < n; j++)
{
// since all four a, b, c,
// d should be distinct
if (i == j)
continue;
for (int k = j + 1; k < n; k++)
{
if (i == k)
continue;
for (int l = k + 1; l < n; l++)
{
if (i == l)
continue;
// if the current combination
// of j, k, l in the set is
// equal to S[i] return this
// value as this would be the
// largest d since we are
// iterating in descending order
if (S[i] == S[j] + S[k] + S[l])
{
found = true;
return S[i];
}
}
}
}
}
if (found == false)
return Integer.MAX_VALUE;
return -1;
}
// Driver Code
public static void main(String []args)
{
// Set of distinct Integers
int []S = new int[]{ 2, 3, 5, 7, 12 };
int n = S.length;
int ans = findLargestd(S, n);
if (ans == Integer.MAX_VALUE)
System.out.println("No Solution");
else
System.out.println("Largest d such that " +
"a + " + "b + c = d is " +
ans );
}
}
// This code is contributed by Sam007
Python3
# Python Program to find the largest
# d such that d = a + b + c
def findLargestd(S, n) :
found = False
# sort the array in ascending order
S.sort()
# iterating from backwards to
# find the required largest d
for i in range(n-1, -1, -1) :
for j in range(0, n) :
# since all four a, b, c,
# d should be distinct
if (i == j) :
continue
for k in range(j + 1, n) :
if (i == k) :
continue
for l in range(k+1, n) :
if (i == l) :
continue
# if the current combination
# of j, k, l in the set is
# equal to S[i] return this
# value as this would be the
# largest d since we are
# iterating in descending order
if (S[i] == S[j] + S[k] + S[l]) :
found = True
return S[i]
if (found == False) :
return -1
# Driver Code
# Set of distinct Integers
S = [ 2, 3, 5, 7, 12 ]
n = len(S)
ans = findLargestd(S, n)
if (ans == -1) :
print ("No Solution")
else :
print ("Largest d such that a + b +" ,
"c = d is" ,ans)
# This code is contributed by Manish Shaw
# (manishshaw1)
C#
// C# Program to find the largest
// such that d = a + b + c
using System;
class GFG
{
// function to find largest d
static int findLargestd(int []S,
int n)
{
bool found = false;
// sort the array
// in ascending order
Array.Sort(S);
// iterating from backwards to
// find the required largest d
for (int i = n - 1; i >= 0; i--)
{
for (int j = 0; j < n; j++)
{
// since all four a, b, c,
// d should be distinct
if (i == j)
continue;
for (int k = j + 1; k < n; k++)
{
if (i == k)
continue;
for (int l = k + 1; l < n; l++)
{
if (i == l)
continue;
// if the current combination
// of j, k, l in the set is
// equal to S[i] return this
// value as this would be the
// largest dsince we are
// iterating in descending order
if (S[i] == S[j] + S[k] + S[l])
{
found = true;
return S[i];
}
}
}
}
}
if (found == false)
return int.MaxValue;
return -1;
}
// Driver Code
public static void Main()
{
// Set of distinct Integers
int []S = new int[]{ 2, 3, 5, 7, 12 };
int n = S.Length;
int ans = findLargestd(S, n);
if (ans == int.MaxValue)
Console.WriteLine( "No Solution");
else
Console.Write("Largest d such that a + " +
"b + c = d is " + ans );
}
}
// This code is contributed by Sam007
PHP
<?php
// PHP Program to find the largest
// d such that d = a + b + c
function findLargestd( $S, $n)
{
$found = false;
// sort the array in
// ascending order
sort($S);
// iterating from backwards to
// find the required largest d
for ( $i = $n - 1; $i >= 0; $i--)
{
for ( $j = 0; $j < $n; $j++)
{
// since all four a, b, c,
// d should be distinct
if ($i == $j)
continue;
for ( $k = $j + 1; $k < $n; $k++)
{
if ($i == $k)
continue;
for ( $l = $k + 1; $l < $n; $l++)
{
if ($i == $l)
continue;
// if the current combination
// of j, k, l in the set is
// equal to S[i] return this
// value as this would be the
// largest d since we are
// iterating in descending order
if ($S[$i] == $S[$j] + $S[$k] + $S[$l])
{
$found = true;
return $S[$i];
}
}
}
}
}
if ($found == false)
return PHP_INT_MIN;
}
// Driver Code
// Set of distinct Integers
$S = array( 2, 3, 5, 7, 12 );
$n = count($S);
$ans = findLargestd($S, $n);
if ($ans == PHP_INT_MIN)
echo "No Solution" ;
else
echo "Largest d such that a + b + " ,
"c = d is " , $ans ;
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript Program to find the largest
// such that d = a + b + c
// function to find largest d
function findLargestd(S, n)
{
let found = false;
// sort the array
// in ascending order
S.sort();
// iterating from backwards to
// find the required largest d
for (let i = n - 1; i >= 0; i--)
{
for (let j = 0; j < n; j++)
{
// since all four a, b, c,
// d should be distinct
if (i == j)
continue;
for (let k = j + 1; k < n; k++)
{
if (i == k)
continue;
for (let l = k + 1; l < n; l++)
{
if (i == l)
continue;
// if the current combination
// of j, k, l in the set is
// equal to S[i] return this
// value as this would be the
// largest dsince we are
// iterating in descending order
if (S[i] == S[j] + S[k] + S[l])
{
found = true;
return S[i];
}
}
}
}
}
if (found == false)
return Number.MAX_VALUE;
return -1;
}
// Set of distinct Integers
let S = [ 2, 3, 5, 7, 12 ];
let n = S.length;
let ans = findLargestd(S, n);
if (ans == Number.MAX_VALUE)
document.write( "No Solution");
else
document.write("Largest d such that a + " +
"b + c = d is " + ans );
</script>
Producción :
Largest d such that a + b + c = d is 12
Esta solución de fuerza bruta tiene una complejidad de tiempo de O((tamaño del Conjunto) 4 ).
Método 2 (Enfoque eficiente: uso de hashing)
El enunciado del problema anterior (a + b + c = d) se puede reformular como encontrar a, b, c, d tal que a + b = d – c. Entonces, este problema se puede resolver de manera eficiente usando hashing.
- Almacene las sumas de todos los pares (a + b) en una tabla hash
- Recorra todos los pares (c, d) nuevamente y busque (d – c) en la tabla hash.
- Si se encuentra un par con la suma requerida, asegúrese de que todos los elementos sean elementos de array distintos y que un elemento no se considere más de una vez.
A continuación se muestra la implementación del enfoque anterior.
C++
// A hashing based CPP program to find largest d
// such that a + b + c = d.
#include <bits/stdc++.h>
using namespace std;
// The function finds four elements with given sum X
int findFourElements(int arr[], int n)
{
// Store sums (a+b) of all pairs (a,b) in a
// hash table
unordered_map<int, pair<int, int> > mp;
for (int i = 0; i < n - 1; i++)
for (int j = i + 1; j < n; j++)
mp[arr[i] + arr[j]] = { i, j };
// Traverse through all pairs and find (d -c)
// is present in hash table
int d = INT_MIN;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
int abs_diff = abs(arr[i] - arr[j]);
// If d - c is present in hash table,
if (mp.find(abs_diff) != mp.end()) {
// Making sure that all elements are
// distinct array elements and an element
// is not considered more than once.
pair<int, int> p = mp[abs_diff];
if (p.first != i && p.first != j &&
p.second != i && p.second != j)
d = max(d, max(arr[i], arr[j]));
}
}
}
return d;
}
// Driver program to test above function
int main()
{
int arr[] = { 2, 3, 5, 7, 12 };
int n = sizeof(arr) / sizeof(arr[0]);
int res = findFourElements(arr, n);
if (res == INT_MIN)
cout << "No Solution.";
else
cout << res;
return 0;
}
Java
// A hashing based Java program to find largest d
// such that a + b + c = d.
import java.util.HashMap;
import java.lang.Math;
// To store and retrieve indices pair i & j
class Indexes
{
int i, j;
Indexes(int i, int j)
{
this.i = i;
this.j = j;
}
int getI()
{
return i;
}
int getJ()
{
return j;
}
}
class GFG {
// The function finds four elements with given sum X
static int findFourElements(int[] arr, int n)
{
HashMap<Integer, Indexes> map = new HashMap<>();
// Store sums (a+b) of all pairs (a,b) in a
// hash table
for (int i = 0; i < n - 1; i++)
{
for (int j = i + 1; j < n; j++)
{
map.put(arr[i] + arr[j], new Indexes(i, j));
}
}
int d = Integer.MIN_VALUE;
// Traverse through all pairs and find (d -c)
// is present in hash table
for (int i = 0; i < n - 1; i++)
{
for (int j = i + 1; j < n; j++)
{
int abs_diff = Math.abs(arr[i] - arr[j]);
// If d - c is present in hash table,
if (map.containsKey(abs_diff))
{
Indexes indexes = map.get(abs_diff);
// Making sure that all elements are
// distinct array elements and an element
// is not considered more than once.
if (indexes.getI() != i && indexes.getI() != j &&
indexes.getJ() != i && indexes.getJ() != j)
{
d = Math.max(d, Math.max(arr[i], arr[j]));
}
}
}
}
return d;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 2, 3, 5, 7, 12 };
int n = arr.length;
int res = findFourElements(arr, n);
if (res == Integer.MIN_VALUE)
System.out.println("No Solution");
else
System.out.println(res);
}
}
// This code is contributed by Vivekkumar Singh
Python3
# A hashing based Python3 program to find
# largest d, such that a + b + c = d.
# The function finds four elements
# with given sum X
def findFourElements(arr, n):
# Store sums (a+b) of all pairs (a,b) in a
# hash table
mp = dict()
for i in range(n - 1):
for j in range(i + 1, n):
mp[arr[i] + arr[j]] =(i, j)
# Traverse through all pairs and find (d -c)
# is present in hash table
d = -10**9
for i in range(n - 1):
for j in range(i + 1, n):
abs_diff = abs(arr[i] - arr[j])
# If d - c is present in hash table,
if abs_diff in mp.keys():
# Making sure that all elements are
# distinct array elements and an element
# is not considered more than once.
p = mp[abs_diff]
if (p[0] != i and p[0] != j and
p[1] != i and p[1] != j):
d = max(d, max(arr[i], arr[j]))
return d
# Driver Code
arr = [2, 3, 5, 7, 12]
n = len(arr)
res = findFourElements(arr, n)
if (res == -10**9):
print("No Solution.")
else:
print(res)
# This code is contributed by Mohit Kumar
C#
// A hashing based C# program to find
// largest d such that a + b + c = d.
using System;
using System.Collections.Generic;
// To store and retrieve
// indices pair i & j
public class Indexes
{
int i, j;
public Indexes(int i, int j)
{
this.i = i;
this.j = j;
}
public int getI()
{
return i;
}
public int getJ()
{
return j;
}
}
public class GFG
{
// The function finds four elements
// with given sum X
static int findFourElements(int[] arr, int n)
{
Dictionary<int, Indexes> map =
new Dictionary<int, Indexes>();
// Store sums (a+b) of all pairs
// (a,b) in a hash table
for (int i = 0; i < n - 1; i++)
{
for (int j = i + 1; j < n; j++)
{
map.Add(arr[i] + arr[j],
new Indexes(i, j));
}
}
int d = int.MinValue;
// Traverse through all pairs and
// find (d -c) is present in hash table
for (int i = 0; i < n - 1; i++)
{
for (int j = i + 1; j < n; j++)
{
int abs_diff = Math.Abs(arr[i] - arr[j]);
// If d - c is present in hash table,
if (map.ContainsKey(abs_diff))
{
Indexes indexes = map[abs_diff];
// Making sure that all elements are
// distinct array elements and an element
// is not considered more than once.
if (indexes.getI() != i &&
indexes.getI() != j &&
indexes.getJ() != i &&
indexes.getJ() != j)
{
d = Math.Max(d, Math.Max(arr[i],
arr[j]));
}
}
}
}
return d;
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 2, 3, 5, 7, 12 };
int n = arr.Length;
int res = findFourElements(arr, n);
if (res == int.MinValue)
Console.WriteLine("No Solution");
else
Console.WriteLine(res);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// A hashing based Javascript program to find largest d
// such that a + b + c = d.
// To store and retrieve indices pair i & j
class Indexes
{
constructor(i,j)
{
this.i = i;
this.j = j;
}
getI()
{
return this.i;
}
getJ()
{
return this.j;
}
}
// The function finds four elements with given sum X
function findFourElements(arr,n)
{
let map = new Map();
// Store sums (a+b) of all pairs (a,b) in a
// hash table
for (let i = 0; i < n - 1; i++)
{
for (let j = i + 1; j < n; j++)
{
map.set(arr[i] + arr[j], new Indexes(i, j));
}
}
let d = Number.MIN_VALUE;
// Traverse through all pairs and find (d -c)
// is present in hash table
for (let i = 0; i < n - 1; i++)
{
for (let j = i + 1; j < n; j++)
{
let abs_diff = Math.abs(arr[i] - arr[j]);
// If d - c is present in hash table,
if (map.has(abs_diff))
{
let indexes = map.get(abs_diff);
// Making sure that all elements are
// distinct array elements and an element
// is not considered more than once.
if (indexes.getI() != i && indexes.getI() != j &&
indexes.getJ() != i && indexes.getJ() != j)
{
d = Math.max(d, Math.max(arr[i], arr[j]));
}
}
}
}
return d;
}
// Driver code
let arr=[ 2, 3, 5, 7, 12];
let n = arr.length;
let res = findFourElements(arr, n);
if (res == Number.MIN_VALUE)
document.write("No Solution");
else
document.write(res);
// This code is contributed by patel2127
</script>
Producción:
12
La complejidad de tiempo total para este enfoque eficiente es O(N 2 ) (donde N es el tamaño del conjunto).
Publicación traducida automáticamente
Artículo escrito por Nishant Tanwar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA