|
This post is completed by 1 user
|
Add to List |
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(N2)
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