This post is completed by 2 users

  • 0
Add to List
Beginner

511. Sum of all the overlapping elements

Given two arrays of integers. Write a program to find the sum of all the overlapping elements between two arrays. You can consider that there will not be any duplicates in each array individually.

Example:

A [] : [6, 5, 1, 9, 2, 8, 3]
B [] : [3, 7, 9, 2, 4]
Overlapping sum of two arrays: 28
(Overlapping elements are 9, 2, 3)

A [] : [6, 5]
B [] : [3, 7]
Overlapping sum of two arrays: 0
(No overlapping elements)

Approach:

Naive Approach: Use nested loops and compare every element from one array with all the elements in another array and get the sum of overlapping elements.

Time Complexity: O(N2)

Better Approach: Use Set

Iterate through the first array and add all the elements to the HashSet. Now iterate through second array and for each element, if it is present in the set then do sum = sum + element*2. At the end return the sum.

Time Complexity: O(N), Space Complexity: O(N)

Output:

A [] : [6, 5, 1, 9, 2, 8, 3]
B [] : [3, 7, 9, 2, 4]
Overlapping sum of two arrays: 28

Reference: geeksforgeeks