Encuentra la suma superpuesta de dos arrays

Dados dos arreglos A[] y B[] que tienen n elementos únicos cada uno. La tarea es encontrar la suma superpuesta de las dos arrays. Esa es la suma de elementos que es común en ambas arrays.

Nota : los elementos de las arrays son únicos. Esa es la array que no contiene duplicados.

Ejemplos:  

Input : A[] = {1, 5, 3, 8}
        B[] = {5, 4, 6, 7}
Output : 10
Explanation : The element which is common in both arrays is 5.
Therefore, the overlapping sum will be (5+5) = 10

Input : A[] = {1, 5, 3, 8}
        B[] = {5, 1, 8, 3}
Output : 99

Método de fuerza bruta: el enfoque simple es que para cada elemento en A[] verifique si está presente en B[] y si está presente en B[], luego agregue ese número dos veces (una vez para A[] y otra vez para B []) a la suma. Repita este procedimiento para todos los elementos de la array A[]. 

Complejidad de tiempo: O(n^2).

Método eficiente: un método eficiente es usar Hashing. Recorra ambas arrays e inserte los elementos en una tabla hash para realizar un seguimiento del recuento de elementos. Suma los elementos a la suma cuyo número es igual a dos.

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

// CPP program to find overlapping sum
#include <bits/stdc++.h>
using namespace std;
 
// Function for calculating
// overlapping sum of two array
int findSum(int A[], int B[], int n)
{  
    // unordered map to store count of
    // elements
    unordered_map<int,int> hash;
     
    // insert elements of A[] into
    // unordered_map
    for(int i=0;i<n;i++)
    {
        if(hash.find(A[i])==hash.end())
        {
            hash.insert(make_pair(A[i],1));
        }
        else
        {
            hash[A[i]]++;
        }
    }
     
    // insert elements of B[] into
    // unordered_map
    for(int i=0;i<n;i++)
    {
        if(hash.find(B[i])==hash.end())
        {
            hash.insert(make_pair(B[i],1));
        }
        else
        {
            hash[B[i]]++;
        }
    }
 
    // calculate overlapped sum
    int sum = 0;
    for(auto itr = hash.begin(); itr!=hash.end(); itr++)
    {
        if((itr->second)==2)
        {
            sum += (itr->first)*2;
        }
    }
     
    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 overlapping sum
import java.io.*;
import java.util.*;
class GFG
{
   
    // Function for calculating
    // overlapping sum of two array
    static int findSum(int A[], int B[], int n)
    {
       
        // unordered map to store count of 
        // elements
        HashMap<Integer, Integer> hash = new HashMap<>();
       
        // insert elements of A[] into
        // unordered_map
        for(int i = 0; i < n; i++)
        {
            if(!hash.containsKey(A[i]))
            {
                hash.put(A[i], 1);
            }
            else
            {
                hash.put(A[i], hash.get(A[i]) + 1);
            }
        }
       
        // insert elements of B[] into
        // unordered_map
        for(int i = 0; i < n; i++)
        {
            if(!hash.containsKey(B[i]))
            {
                hash.put(B[i], 1);
            }
            else
            {
                hash.put(B[i], hash.get(B[i]) + 1);
            }
        }
       
        // calculate overlapped sum
        int sum = 0;
        for(int itr: hash.keySet())
        {
            if(hash.get(itr) == 2)
            {
                sum += itr * 2;
            }
        }
        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;
        System.out.println(findSum(A, B, n));
    }
}
 
// This code is contributed by rag2127

# Python3 program to find overlapping sum
 
# Function for calculating
# overlapping sum of two array
def findSum(A, B, n):
     
    # unordered map to store count of
    # elements
    hash=dict()
 
    # insert elements of A into
    # unordered_map
    for i in range(n):
        hash[A[i]] = hash.get(A[i], 0) + 1
 
    # insert elements of B into
    # unordered_map
    for i in range(n):
        hash[B[i]] = hash.get(B[i], 0) + 1
 
 
    # calculate overlapped sum
    sum = 0
 
    for i in hash:
        if hash[i] == 2:
            sum += i * 2
 
    return sum
 
# Driver code
 
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 mohit kumar 29

// C# program to find overlapping sum
using System;
using System.Collections.Generic;
public class GFG
{
      
    // Function for calculating
    // overlapping sum of two array
    static int findSum(int[] A, int[] B, int n)
    {
       
        // unordered map to store count of 
        // elements
        Dictionary<int, int> hash = new Dictionary<int, int>();
         
        // insert elements of A[] into
        // unordered_map
        for(int i = 0; i < n; i++)
        {
            if(!hash.ContainsKey(A[i]))
            {
                hash.Add(A[i], 1);
            }
            else
            {
                hash[A[i]]++;
            }
        }
         
        // insert elements of B[] into
        // unordered_map
        for(int i = 0; i < n; i++)
        {
            if(!hash.ContainsKey(B[i]))
            {
                hash.Add(B[i], 1);
            }
            else
            {
                hash[B[i]]++;
            }
        }
         
        // calculate overlapped sum
        int sum = 0;
        foreach(KeyValuePair<int, int> itr in hash)
        {
            if(itr.Value == 2)
            {
                sum += itr.Key * 2;
            }
        }
        return sum;
    }
     
    // Driver code
    static public void Main ()
    {
         int[] A = { 5, 4, 9, 2, 3 };
        int[] B = { 2, 8, 7, 6, 3 };
    
        // size of array
        int n = A.Length;
        Console.Write(findSum(A, B, n));
    }
}
 
// This code is contributed by avanitrachhadiya2155

<script>
 
// Javascript program to find overlapping sum
     
// Function for calculating
// overlapping sum of two array
function findSum(A, B, n)
{
     
    // unordered map to store count of
    // elements
    let hash = new Map();
    
    // Insert elements of A[] into
    // unordered_map
    for(let i = 0; i < n; i++)
    {
        if (!hash.has(A[i]))
        {
            hash.set(A[i], 1);
        }
        else
        {
            hash.set(A[i], hash.get(A[i]) + 1);
        }
    }
    
    // Insert elements of B[] into
    // unordered_map
    for(let i = 0; i < n; i++)
    {
        if (!hash.has(B[i]))
        {
            hash.set(B[i], 1);
        }
        else
        {
            hash.set(B[i], hash.get(B[i]) + 1);
        }
    }
    
    // Calculate overlapped sum
    let sum = 0;
    for(let [key, value] of hash.entries())
    {
        if(value == 2)
        {
            sum += key * 2;
        }
    }
    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;
 
document.write(findSum(A, B, n));
 
// This code is contributed by patel2127
 
</script>

Producción: 

10

Tiempo Complejidad : O(n) 
Espacio Auxiliar : O(n)

Este artículo es una contribución de Shivam Pradhan (anuj_charm) . 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 contribuir@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.