Dada una array de un número par de elementos, forme grupos de 2 usando estos elementos de la array de modo que la diferencia entre el grupo con la suma más alta y el que tiene la suma más baja sea mínima.
Nota: Un elemento puede ser parte de un solo grupo y tiene que ser parte de al menos 1 grupo.
Ejemplos:
Input : arr[] = {2, 6, 4, 3}
Output : 1
Groups formed will be (2, 6) and (4, 3),
the difference between highest sum group
(2, 6) i.e 8 and lowest sum group (3, 4)
i.e 7 is 1.
Input : arr[] = {11, 4, 3, 5, 7, 1}
Output : 3
Groups formed will be (1, 11), (4, 5) and
(3, 7), the difference between highest
sum group (1, 11) i.e 12 and lowest sum
group (4, 5) i.e 9 is 3.
Enfoque simple: un enfoque simple sería probar con todas las combinaciones de elementos de array y verificar con cada conjunto de diferencia de combinación entre el grupo con la suma más alta y el que tiene la suma más baja. Se formarían un total de n*(n-1)/2 de tales grupos (nC2).
Complejidad de tiempo: O (n ^ 3) Para generar grupos, se necesitarán n ^ 2 iteraciones y para verificar cada grupo se necesitarán n iteraciones y, por lo tanto, se necesitarán n ^ 3 iteraciones en el peor de los casos.
Enfoque eficiente: el enfoque eficiente sería utilizar el enfoque codicioso. Ordene toda la array y genere grupos seleccionando un elemento desde el inicio de la array y uno desde el final.
C++
// CPP program to find minimum difference
// between groups of highest and lowest
// sums.
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
ll calculate(ll a[], ll n)
{
// Sorting the whole array.
sort(a, a + n);
// Generating sum groups.
vector<ll> s;
for (int i = 0, j = n - 1; i < j; i++, j--)
s.push_back(a[i] + a[j]);
ll mini = *min_element(s.begin(), s.end());
ll maxi = *max_element(s.begin(), s.end());
return abs(maxi - mini);
}
int main()
{
ll a[] = { 2, 6, 4, 3 };
int n = sizeof(a) / (sizeof(a[0]));
cout << calculate(a, n) << endl;
return 0;
}
Java
// Java program to find minimum
// difference between groups of
// highest and lowest sums.
import java.util.Arrays;
import java.util.Collections;
import java.util.Vector;
class GFG {
static long calculate(long a[], int n)
{
// Sorting the whole array.
Arrays.sort(a);
int i,j;
// Generating sum groups.
Vector<Long> s = new Vector<>();
for (i = 0, j = n - 1; i < j; i++, j--)
s.add((a[i] + a[j]));
long mini = Collections.min(s);
long maxi = Collections.max(s);
return Math.abs(maxi - mini);
}
// Driver code
public static void main(String[] args)
{
long a[] = { 2, 6, 4, 3 };
int n = a.length;
System.out.println(calculate(a, n));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to find minimum # difference between groups of # highest and lowest sums. def calculate(a, n): # Sorting the whole array. a.sort(); # Generating sum groups. s = []; i = 0; j = n - 1; while(i < j): s.append((a[i] + a[j])); i += 1; j -= 1; mini = min(s); maxi = max(s); return abs(maxi - mini); # Driver Code a = [ 2, 6, 4, 3 ]; n = len(a); print(calculate(a, n)); # This is contributed by mits
C#
// C# program to find minimum
// difference between groups of
// highest and lowest sums.
using System;
using System.Linq;
using System.Collections.Generic;
class GFG
{
static long calculate(long []a, int n)
{
// Sorting the whole array.
Array.Sort(a);
int i, j;
// Generating sum groups.
List<long> s = new List<long>();
for (i = 0, j = n - 1; i < j; i++, j--)
s.Add((a[i] + a[j]));
long mini = s.Min();
long maxi = s.Max();
return Math.Abs(maxi - mini);
}
// Driver code
public static void Main()
{
long []a = { 2, 6, 4, 3 };
int n = a.Length;
Console.WriteLine(calculate(a, n));
}
}
//This code is contributed by Rajput-Ji
PHP
<?php
// PHP program to find minimum
// difference between groups of
// highest and lowest sums.
function calculate($a, $n)
{
// Sorting the whole array.
sort($a);
// Generating sum groups.
$s = array();
for ($i = 0, $j = $n - 1;
$i < $j; $i++, $j--)
array_push($s, ($a[$i] + $a[$j]));
$mini = min($s);
$maxi = max($s);
return abs($maxi - $mini);
}
// Driver Code
$a = array( 2, 6, 4, 3 );
$n = sizeof($a);
echo calculate($a, $n);
// This is contributed by mits
?>
Javascript
<script>
// Javascript program to find minimum
// difference between groups of
// highest and lowest sums
function calculate(a, n)
{
// Sorting the whole array.
a.sort();
let i,j;
// Generating sum groups.
let s = [];
for (i = 0, j = n - 1; i < j; i++, j--)
s.push((a[i] + a[j]));
let mini = Math.min(...s);
let maxi = Math.max(...s);
return Math.abs(maxi - mini);
}
// driver code
let a = [ 2, 6, 4, 3 ];
let n = a.length;
document.write(calculate(a, n));
</script>
1
Tiempo Complejidad: O (n * log n)
Espacio Auxiliar: O(n)
Optimización del enfoque anterior: podemos modificar el enfoque eficiente anterior reduciendo el espacio auxiliar de O(n) a O(1). En lugar de empujar todos los grupos en un vector, podemos atravesar directamente la array y realizar un seguimiento de los grupos de elementos máximos y mínimos.
A continuación se muestra el código para el enfoque anterior:
C++
// CPP program to find minimum difference
// between groups of highest and lowest
// sums.
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
ll calculate(ll a[], ll n)
{
// Sorting the whole array.
sort(a, a + n);
ll mini = a[0]+a[n-1];
ll maxi = a[0]+a[n-1];
for (int i = 1, j = n - 2; i < j; i++, j--)
{
if(a[i]+a[j]>maxi)
{
maxi=a[i]+a[j];
}
if(a[i]+a[j]<mini)
{
mini=a[i]+a[j];
}
}
return abs(maxi - mini);
}
int main()
{
ll a[] = { 2, 6, 4, 3 };
int n = sizeof(a) / (sizeof(a[0]));
cout << calculate(a, n) << endl;
return 0;
}
// This code is contributed by Pushpesh Raj
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
static int calculate(int[] a, int n)
{
// sort the array.
Arrays.sort(a);
int mini = a[0] + a[n - 1];
int maxi = a[0] + a[n - 1];
for (int i = 1, j = n - 1; i < j; i++, j--) {
if (a[i] + a[j] > maxi) {
maxi = a[i] + a[j];
}
if (a[i] + a[j] < mini) {
mini = a[i] + a[j];
}
}
return Math.abs(maxi - mini);
}
public static void main(String[] args)
{
int[] a = { 2, 6, 4, 3 };
int n = a.length;
System.out.print(calculate(a, n));
}
}
// This code is contributed by lokesh (lokeshmvs21).
1
Complejidad de tiempo: O (n*log(n))
Espacio Auxiliar: O(1)
Preguntado en: Inmobi
Referencia: https://www.hackerearth.com/problem/algorithm/project-team/
Publicación traducida automáticamente
Artículo escrito por Aditya Gupta 4 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA