Recuento de la suma de pares distintos en una array dada

Dada una array arr[] de tamaño N , la tarea es encontrar el número total de sumas de pares únicos posibles de los elementos de la array.

Ejemplos:

Entrada: arr[] = {6, 1, 4, 3}
Salida: 5
Explicación: Todos los pares posibles son {6, 1}, {6, 4}, {6, 3}, {1, 4}, {1 , 3}, {4, 3}. Las
sumas de estos pares son 7, 10, 9, 5, 4, 7. Entonces sumas únicas 7, 10, 9, 5, 4. Entonces la respuesta es 5.

Entrada: arr[] = {8, 7, 6, 5, 4, 3, 2, 1}
Salida: 13

Enfoque: este problema se puede resolver de manera eficiente utilizando unordered_set . 

Calcula todas las sumas posibles de pares y guárdalas en un conjunto desordenado. Esto se hace para almacenar los elementos de la tienda en un tiempo promedio de O(1) sin que se repita ningún valor. 

Algoritmo:

• Use bucles anidados para obtener todas las sumas posibles de elementos de la array.
• Almacene todas las sumas posibles en un conjunto unordered_set.
• Las sumas únicas posibles totales serían iguales al tamaño de unordered_set. Así que devuelve el tamaño del conjunto desordenado.

A continuación se muestra la implementación del enfoque anterior:

// C++ program to count the pairs with unique sums
#include <bits/stdc++.h>
using namespace std;
  
// Function to return the
// total count of required pairs
int count(int arr[], int n)
{
    unordered_set<int> s;
    // Add all possible sums into the set
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            s.insert(arr[i] + arr[j]);
        }
    }
    // Return the size of set
    return s.size();
}
  
// Driver code
int main()
{
    int arr[] = { 6, 1, 4, 3 };
    int N = sizeof(arr) / sizeof(arr[0]);
  
    // Function call
    cout << count(arr, N);
    return 0;
}

// Java program to find Count the pairs
// with unique sums
import java.util.*;
  
class GFG {
    // Function to return the
    // total count of required pairs
    static int count(int arr[], int n)
    {
        Set<Integer> s = new HashSet<Integer>();
  
        // Add all possible sums into the set
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                s.add(arr[i] + arr[j]);
            }
        }
        // Return the size of set
        return s.size();
    }
  
    // Driver code
    public static void main(String args[])
    {
        int arr[] = { 6, 1, 4, 3 };
        int N = arr.length;
  
        // Function call
        System.out.println(count(arr, N));
    }
}

# Python program to find Count the pairs
# with unique sums
  
# Function to return the 
# total count of required pairs
def count(arr, n):
    s = set()
      
    # Add all possible sums into the set
    for i in range(n-1):
        for j in range(i + 1, n):
            s.add(arr[i] + arr[j])
  
    # Return the size of set
    return int(len(s))
  
# Driver code
if __name__ == '__main__':
    arr = [6, 1, 4, 3]
    N = len(arr)
      
    # Function call
    print(count(arr, N))

<script>
  
// JavaScript program to find Count the pairs
// with unique sums
  
// Function to return the 
// total count of required pairs
function count(arr, n) {
    let s = new Set();
    // Add all possible sums into the set
    for (let i = 0; i < n - 1; i++) {
        for (let j = i + 1; j < n; j++) {
            s.add(arr[i] + arr[j]);
        }
    }
    // Return the size of set
    return s.size;
}
  
// Driver code
let arr = [6, 1, 4, 3];
let N = arr.length;
  
// Function call
document.write(count(arr, N));
  
</script>

5

Complejidad temporal: O(N ² )
Espacio auxiliar: O(N)