Non-overlapping sum of two sets
Last Updated :
20 Jan, 2023
Given two arrays A[] and B[] of size n. It is given that both array individually contains distinct elements. We need to find the sum of all elements that are not common.
Examples:
Input : A[] = {1, 5, 3, 8}
B[] = {5, 4, 6, 7}
Output : 29
1 + 3 + 4 + 6 + 7 + 8 = 29
Input : A[] = {1, 5, 3, 8}
B[] = {5, 1, 8, 3}
Output : 0
All elements are common.
Brute Force Method: One simple approach is that for each element in A[] check whether it is present in B[], if it is present in then add it to the result. Similarly, traverse B[] and for every element that is not present in B, add it to result.
Time Complexity: O(n2).
Auxiliary Space: O(1), As constant extra space is used.
Hashing concept: Create an empty hash and insert elements of both arrays into it. Now traverse hash table and add all those elements whose count is 1. (As per the question, both arrays individually have distinct elements)
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
int findSum(int A[], int B[], int n)
{
unordered_map<int, int> hash;
for (int i = 0; i < n; i++) {
hash[A[i]]++;
hash[B[i]]++;
}
int sum = 0;
for (auto x: hash)
if (x.second == 1)
sum += x.first;
return sum;
}
int main()
{
int A[] = { 5, 4, 9, 2, 3 };
int B[] = { 2, 8, 7, 6, 3 };
int n = sizeof(A) / sizeof(A[0]);
cout << findSum(A, B, n);
return 0;
}
|
Java
import java.io.*;
import java.util.*;
class GFG
{
static int findSum(int[] A, int[] B, int n)
{
HashMap<Integer, Integer> hash = new HashMap<>();
for (int i = 0; i < n; i++)
{
if (hash.containsKey(A[i]))
hash.put(A[i], 1 + hash.get(A[i]));
else
hash.put(A[i], 1);
if (hash.containsKey(B[i]))
hash.put(B[i], 1 + hash.get(B[i]));
else
hash.put(B[i], 1);
}
int sum = 0;
for (Map.Entry entry : hash.entrySet())
{
if (Integer.parseInt((entry.getValue()).toString()) == 1)
sum += Integer.parseInt((entry.getKey()).toString());
}
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
from collections import defaultdict
def findSum(A, B, n):
Hash = defaultdict(lambda:0)
for i in range(0, n):
Hash[A[i]] += 1
Hash[B[i]] += 1
Sum = 0
for x in Hash:
if Hash[x] == 1:
Sum += x
return Sum
if __name__ == "__main__":
A = [5, 4, 9, 2, 3]
B = [2, 8, 7, 6, 3]
n = len(A)
print(findSum(A, B, n))
|
C#
using System;
using System.Collections.Generic;
class GFG
{
static int findSum(int[] A, int[] B, int n)
{
Dictionary<int, int> hash = new Dictionary<int, int>();
for (int i = 0; i < n; i++)
{
if (hash.ContainsKey(A[i]))
{
var v = hash[A[i]];
hash.Remove(A[i]);
hash.Add(A[i], 1 + v);
}
else
hash.Add(A[i], 1);
if (hash.ContainsKey(B[i]))
{
var v = hash[B[i]];
hash.Remove(B[i]);
hash.Add(B[i], 1 + v);
}
else
hash.Add(B[i], 1);
}
int sum = 0;
foreach(KeyValuePair<int, int> entry in hash)
{
if ((entry.Value) == 1)
sum += entry.Key;
}
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
<script>
function findSum(A, B, n) {
let hash = new Map();
for (let i = 0; i < n; i++) {
if (hash.has(A[i]))
hash.set(A[i], 1 + hash.get(A[i]));
else
hash.set(A[i], 1);
if (hash.has(B[i]))
hash.set(B[i], 1 + hash.get(B[i]));
else
hash.set(B[i], 1);
}
let sum = 0;
for (let entry of hash) {
if (parseInt((entry[1]).toString()) == 1)
sum += parseInt((entry[0]).toString());
}
return sum;
}
let A = [5, 4, 9, 2, 3];
let B = [2, 8, 7, 6, 3];
let n = A.length;
document.write(findSum(A, B, n));
</script>
|
Time Complexity: O(n), since inserting in an unordered map is amortized constant.
Auxiliary Space: O(n).
Another method: Using set data structure
- Insert elements of Array A in the set data structure and add into sum
- Check if B’s elements are there in set if exist then remove current element from set, otherwise add current element to sum
- Finally, return sum
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
int findSum(int A[], int B[], int n)
{
int sum = 0;
set<int> st;
for (int i = 0; i < n; i++) {
st.insert(A[i]);
sum += A[i];
}
for (int i = 0; i < n; i++) {
if (st.find(B[i]) == st.end()) {
sum += B[i];
}
else {
sum -= B[i];
}
}
return sum;
}
int main()
{
int A[] = { 5, 4, 9, 2, 3 };
int B[] = { 2, 8, 7, 6, 3 };
int n = sizeof(A) / sizeof(A[0]);
cout << findSum(A, B, n);
return 0;
}
|
Java
import java.io.*;
import java.util.*;
class GFG {
public static int findSum(int[] A, int[] B, int n) {
int sum = 0;
Set<Integer> st = new HashSet<>();
for (int i = 0; i < n; i++) {
st.add(A[i]);
sum += A[i];
}
for (int i = 0; i < n; i++) {
if (!st.contains(B[i])) {
sum += B[i];
}
else {
sum -= B[i];
}
}
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
def findSum(A, B, n):
sum = 0;
st = set();
for i in range(0,n):
st.add(A[i]);
sum += A[i];
for i in range (0, n):
if (B[i] in st):
sum -= B[i];
else :
sum += B[i];
return sum;
A = [ 5, 4, 9, 2, 3 ];
B = [ 2, 8, 7, 6, 3 ];
n = len(A);
print(findSum(A, B, n));
|
C#
Javascript
<div id="highlighter_664145" class="syntaxhighlighter nogutter "><table border="0" cellpadding="0" cellspacing="0"><tbody><tr><td class="code"><div class="container"><div class="line number1 index0 alt2"><code class="comments">
|
Time Complexity: O(n*log n)
Auxiliary Space: O(n)
Please Login to comment...