Suma no superpuesta de dos conjuntos

Dadas dos arrays A[] y B[] de tamaño n. Se da que ambas arrays contienen elementos distintos individualmente. Necesitamos encontrar la suma de todos los elementos que no son comunes.

Ejemplos: 

Input : A[] = {1, 5, 3, 8}
        B[] = {5, 4, 6, 7}
Output : 29
1 + 3 + 4 + 6 + 7 + 8 = 29

Input : A[] = {1, 5, 3, 8}
        B[] = {5, 1, 8, 3}
Output : 0
All elements are common.

Método de fuerza bruta: un enfoque simple es que para cada elemento en A[] verifique si está presente en B[], si está presente, luego agréguelo al resultado. De manera similar, recorra B[] y para cada elemento que no esté presente en B, agréguelo al resultado. 
Complejidad Temporal: O(n ² ).

Concepto de hashing: cree un hash vacío e inserte elementos de ambas arrays en él. Ahora recorra la tabla hash y agregue todos los elementos cuyo recuento sea 1. (Según la pregunta, ambas arrays tienen elementos distintos individualmente)

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

// CPP program to find Non-overlapping sum
#include <bits/stdc++.h>
using namespace std;
 
 
// function for calculating
// Non-overlapping sum of two array
int findSum(int A[], int B[], int n)
{
    // Insert elements of both arrays
    unordered_map<int, int> hash;   
    for (int i = 0; i < n; i++) {
        hash[A[i]]++;
        hash[B[i]]++;
    }
 
    // calculate non-overlapped sum
    int sum = 0;
    for (auto x: hash)
        if (x.second == 1)
            sum += x.first;
     
    return sum;
}
 
// driver code
int main()
{
    int A[] = { 5, 4, 9, 2, 3 };
    int B[] = { 2, 8, 7, 6, 3 };
     
    // size of array
    int n = sizeof(A) / sizeof(A[0]);
 
    // function call
    cout << findSum(A, B, n);
    return 0;
}

// Java program to find Non-overlapping sum
import java.io.*;
import java.util.*;
 
class GFG
{
 
    // function for calculating
    // Non-overlapping sum of two array
    static int findSum(int[] A, int[] B, int n)
    {
        // Insert elements of both arrays
        HashMap<Integer, Integer> hash = new HashMap<>();
        for (int i = 0; i < n; i++)
        {
            if (hash.containsKey(A[i]))
                hash.put(A[i], 1 + hash.get(A[i]));
            else
                hash.put(A[i], 1);
 
            if (hash.containsKey(B[i]))
                hash.put(B[i], 1 + hash.get(B[i]));
            else
                hash.put(B[i], 1);
        }
 
        // calculate non-overlapped sum
        int sum = 0;
        for (Map.Entry entry : hash.entrySet())
        {
            if (Integer.parseInt((entry.getValue()).toString()) == 1)
                sum += Integer.parseInt((entry.getKey()).toString());
        }
 
        return sum;
 
    }
 
    // Driver code
    public static void main(String args[])
    {
        int[] A = { 5, 4, 9, 2, 3 };
        int[] B = { 2, 8, 7, 6, 3 };
 
        // size of array
        int n = A.length;
 
        // function call
        System.out.println(findSum(A, B, n));
    }
}
 
// This code is contributed by rachana soma

# Python3 program to find Non-overlapping sum
from collections import defaultdict
 
# Function for calculating
# Non-overlapping sum of two array
def findSum(A, B, n):
 
    # Insert elements of both arrays
    Hash = defaultdict(lambda:0)
    for i in range(0, n):
        Hash[A[i]] += 1
        Hash[B[i]] += 1
 
    # calculate non-overlapped sum
    Sum = 0
    for x in Hash:
        if Hash[x] == 1:
            Sum += x
     
    return Sum
 
# Driver code
if __name__ == "__main__":
 
    A = [5, 4, 9, 2, 3]
    B = [2, 8, 7, 6, 3]
     
    # size of array
    n = len(A)
 
    # Function call
    print(findSum(A, B, n))
     
# This code is contributed
# by Rituraj Jain

// C# program to find Non-overlapping sum
using System;
using System.Collections.Generic;
     
class GFG
{
 
    // function for calculating
    // Non-overlapping sum of two array
    static int findSum(int[] A, int[] B, int n)
    {
        // Insert elements of both arrays
        Dictionary<int, int> hash = new Dictionary<int, int>();
        for (int i = 0; i < n; i++)
        {
            if (hash.ContainsKey(A[i]))
            {
                var v = hash[A[i]];
                hash.Remove(A[i]);
                hash.Add(A[i], 1 + v);
            }
            else
                hash.Add(A[i], 1);
 
            if (hash.ContainsKey(B[i]))
            {
                var v = hash[B[i]];
                hash.Remove(B[i]);
                hash.Add(B[i], 1 + v);
            }
            else
                hash.Add(B[i], 1);
        }
 
        // calculate non-overlapped sum
        int sum = 0;
        foreach(KeyValuePair<int, int> entry in hash)
        {
            if ((entry.Value) == 1)
                sum += entry.Key;
        }
 
        return sum;
 
    }
 
    // Driver code
    public static void Main(String []args)
    {
        int[] A = { 5, 4, 9, 2, 3 };
        int[] B = { 2, 8, 7, 6, 3 };
 
        // size of array
        int n = A.Length;
 
        // function call
        Console.WriteLine(findSum(A, B, n));
    }
}
 
// This code is contributed by 29AjayKumar

<script>
 
// JavaScript program to find Non-overlapping sum
 
// function for calculating
// Non-overlapping sum of two array
function findSum(A, B, n) {
    // Insert elements of both arrays
    let hash = new Map();
    for (let i = 0; i < n; i++) {
        if (hash.has(A[i]))
            hash.set(A[i], 1 + hash.get(A[i]));
        else
            hash.set(A[i], 1);
 
        if (hash.has(B[i]))
            hash.set(B[i], 1 + hash.get(B[i]));
        else
            hash.set(B[i], 1);
    }
 
    // calculate non-overlapped sum
    let sum = 0;
    for (let entry of hash) {
        if (parseInt((entry[1]).toString()) == 1)
            sum += parseInt((entry[0]).toString());
    }
 
    return sum;
 
}
 
// Driver code
 
let A = [5, 4, 9, 2, 3];
let B = [2, 8, 7, 6, 3];
 
// size of array
let n = A.length;
 
// function call
document.write(findSum(A, B, n));
 
// This code is contributed by gfgking
 
</script>

39

Complejidad Temporal: O(n), ya que la inserción en un mapa desordenado se amortiza constante.
Espacio Auxiliar: O(n).

Este artículo es una contribución de Aarti_Rathi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.