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. |
Output
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> |
Output
10
Complexity Analysis:
- Time Complexity: O(n)
- Auxiliary Space: O(n)
This article is contributed by Shivam Pradhan (anuj_charm). If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
