Find the overlapping sum of two arrays
Given two arrays A[] and B[] having n unique elements each. The task is to find the overlapping sum of the two arrays. That is the sum of elements that is common in both of the arrays.
Note: Elements in the arrays are unique. That is the array does not contain duplicates.
Examples:
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 : 34
Brute Force Method: The simple approach is that for each element in A[] check whether it is present in B[] and if it is present in B[] then add that number two times(once for A[] and once for B[]) to the sum. Repeat this procedure for all elements in array A[].
C++
// 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) { int sum = 0; for ( int i = 0; i < n; i++) { for ( int j = 0; j < n; j++) { if (A[i] == B[j]) { sum += 2 * A[i]; break ; } } } 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
/*package whatever //do not write package name here */ import java.io.*; class Gfg { public static int findSum( int [] A, int [] B, int n) { int sum = 0 ; for ( int i = 0 ; i < n; i++) { for ( int j = 0 ; j < n; j++) { if (A[i] == B[j]) { sum += 2 * A[i]; break ; } } } return sum; } public static void main(String[] args) { int [] A = { 5 , 4 , 9 , 2 , 3 }; int [] B = { 2 , 8 , 7 , 6 , 3 }; int n = A.length; System.out.println(findSum(A, B, n)); } } |
Python3
# Python program to find overlapping sum # Function for calculating # overlapping sum of two array def findSum( A, B, n): sum = 0 ; for i in range ( 0 ,n): for j in range ( 0 ,n): if (A[i] = = B[j]): sum + = 2 * A[i]; break ; 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 ratiagrawal. |
C#
using System; public class Gfg { public static int findSum( int [] A, int [] B, int n) { int sum = 0; for ( int i = 0; i < n; i++) { for ( int j = 0; j < n; j++) { if (A[i] == B[j]) { sum += 2 * A[i]; break ; } } } return sum; } public static void Main( string [] args) { int [] A = { 5, 4, 9, 2, 3 }; int [] B = { 2, 8, 7, 6, 3 }; int n = A.Length; Console.WriteLine(findSum(A, B, n)); } } |
Javascript
// Javascript program to find overlapping sum // Function for calculating // overlapping sum of two array function findSum( A, B, n) { let sum = 0; for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) { if (A[i] == B[j]) { sum += 2 * A[i]; break ; } } } 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 console.log(findSum(A, B, n)); // This code is contributed by poojaagrawal2. |
10
Time Complexity: O(n^2).
Auxiliary Space: O(1)
Efficient Method: An efficient method is to use Hashing. Traverse both of the arrays and insert the elements into a hash table to keep track of the count of elements. Add the elements to sum whose count equals to two.
Below is the implementation of the above approach:
C++
// 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
// 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
# 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#
// 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 |
Javascript
<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> |
10
Complexity Analysis:
- Time Complexity: O(n)
- Auxiliary Space: O(n)