464. Sum of distinct elements among two given sets

Objective: Given two sets of elements, find the sum of all distinct elements from the set. In other words, find the sum of all elements which are present in either of the given set. 

This problem is also asked as - Find sum of non-overlapping numbers in two given sets.

Example:

Set 1 : [3, 1, 7, 9], Set 2: [2, 4, 1, 9, 3]
Output: 13 (distinct elements - 4, 7, 2 )

Naive Approach: Brute Force - Initialize sum = 0. Compare each element of set one with the second set and if element is not present then add that element to sum. Then do the vice versa to add elements from the second set. 

Time Complexity: O(N²)

Better Approach: Use Map.

• Create a map.
• Insert all the elements from both the sets with the element as key and its count (in both arrays).
• Now iterate through the constructed map and sum all the elements with count = 1.

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

Output:

Set 1: [3, 1, 7, 9], Set 2: [2, 4, 1, 9, 3]
Distinct Elements Sum : 13

Related Problems:

- In an array, Duplicate the zeroes without expanding it Beginner
- Linear Search vs Binary Search Beginner
- All Paths from Top Left to Bottom Right in 2D Array Medium
- Find the Kth Smallest/Largest Element in an Array Using Heap Beginner
- Rearrange Array: Positive and Negative Elements Alternating Hard