Non-overlapping sum of two sets
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++
// CPP program to find Non-overlapping sum #include <bits/stdc++.h> using namespace std; // function for calculating // Non-overlapping sum of two array int findSum( int A[], int B[], int n) { // Insert elements of both arrays unordered_map< int , int > hash; for ( int i = 0; i < n; i++) { hash[A[i]]++; hash[B[i]]++; } // calculate non-overlapped sum int sum = 0; for ( auto x: hash) if (x.second == 1) sum += x.first; 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 Non-overlapping sum import java.io.*; import java.util.*; class GFG { // function for calculating // Non-overlapping sum of two array static int findSum( int [] A, int [] B, int n) { // Insert elements of both arrays 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 ); } // calculate non-overlapped sum int sum = 0 ; for (Map.Entry entry : hash.entrySet()) { if (Integer.parseInt((entry.getValue()).toString()) == 1 ) sum += Integer.parseInt((entry.getKey()).toString()); } 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; // function call System.out.println(findSum(A, B, n)); } } // This code is contributed by rachana soma |
Python3
# Python3 program to find Non-overlapping sum from collections import defaultdict # Function for calculating # Non-overlapping sum of two array def findSum(A, B, n): # Insert elements of both arrays Hash = defaultdict( lambda : 0 ) for i in range ( 0 , n): Hash [A[i]] + = 1 Hash [B[i]] + = 1 # calculate non-overlapped sum Sum = 0 for x in Hash : if Hash [x] = = 1 : Sum + = x return Sum # Driver code if __name__ = = "__main__" : 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 Rituraj Jain |
C#
// C# program to find Non-overlapping sum using System; using System.Collections.Generic; class GFG { // function for calculating // Non-overlapping sum of two array static int findSum( int [] A, int [] B, int n) { // Insert elements of both arrays 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); } // calculate non-overlapped sum int sum = 0; foreach (KeyValuePair< int , int > entry in hash) { if ((entry.Value) == 1) sum += entry.Key; } 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; // function call Console.WriteLine(findSum(A, B, n)); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript program to find Non-overlapping sum // function for calculating // Non-overlapping sum of two array function findSum(A, B, n) { // Insert elements of both arrays 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); } // calculate non-overlapped sum let sum = 0; for (let entry of hash) { if (parseInt((entry[1]).toString()) == 1) sum += parseInt((entry[0]).toString()); } 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 document.write(findSum(A, B, n)); // This code is contributed by gfgking </script> |
39
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++
// CPP program to find Non-overlapping sum #include <bits/stdc++.h> using namespace std; // function for calculating // Non-overlapping sum of two array int findSum( int A[], int B[], int n) { int sum = 0; // Insert elements of Array A in set // and add into sum set< int > st; for ( int i = 0; i < n; i++) { st.insert(A[i]); sum += A[i]; } // Check if B's element are there in set // if exist then remove current element from // set, otherwise add current element into sum for ( int i = 0; i < n; i++) { if (st.find(B[i]) == st.end()) { sum += B[i]; } else { sum -= B[i]; } } // Finally, return sum 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; } // This code is contributed by hkdass001 |
Java
// Java program to find Non-overlapping sum import java.io.*; import java.util.*; class GFG { // function for calculating // Non-overlapping sum of two array public static int findSum( int [] A, int [] B, int n) { int sum = 0 ; // Insert elements of Array A in set // and add into sum Set<Integer> st = new HashSet<>(); for ( int i = 0 ; i < n; i++) { st.add(A[i]); sum += A[i]; } // Check if B's element are there in set // if exist then remove current element from // set, otherwise add current element into sum for ( int i = 0 ; i < n; i++) { if (!st.contains(B[i])) { sum += B[i]; } else { sum -= B[i]; } } // Finally, return sum return sum; } 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; // function call System.out.println(findSum(A, B, n)); } } // This code is contributed by lokesh. |
Python3
# python program to find Non-overlapping sum # function for calculating # Non-overlapping sum of two array def findSum(A, B, n): sum = 0 ; # Insert elements of Array A in set # and add into sum st = set (); for i in range ( 0 ,n): st.add(A[i]); sum + = A[i]; # Check if B's element are there in set # if exist then remove current element from # set, otherwise add current element into sum for i in range ( 0 , n): if (B[i] in st): sum - = B[i]; else : sum + = B[i]; # Finally, return sum 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)); |
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" > // Javascript program to find Non-overlapping sum</code></div><div class="line number2 index1 alt1"> </div><div class="line number3 index2 alt2"><code class="comments">// function for calculating</code></div><div class="line number4 index3 alt1"><code class="comments">// Non-overlapping sum of two array</code></div><div class="line number5 index4 alt2"><code class="keyword">function</code> <code class="plain">findSum(A, B, n)</code></div><div class="line number6 index5 alt1"><code class="plain">{</code></div><div class="line number7 index6 alt2"><code class="undefined spaces"> </code><code class="plain">let sum = 0;</code></div><div class="line number8 index7 alt1"> </div><div class="line number9 index8 alt2"><code class="undefined spaces"> </code><code class="comments">// Insert elements of Array A in set</code></div><div class="line number10 index9 alt1"><code class="undefined spaces"> </code><code class="comments">// and add into sum</code></div><div class="line number11 index10 alt2"><code class="undefined spaces"> </code><code class="plain">let st = </code><code class="keyword">new</code> <code class="plain">Set();</code></div><div class="line number12 index11 alt1"><code class="undefined spaces"> </code><code class="keyword">for</code> <code class="plain">(let i = 0; i < n; i++) {</code></div><div class="line number13 index12 alt2"><code class="undefined spaces"> </code><code class="plain">st.add(A[i]);</code></div><div class="line number14 index13 alt1"><code class="undefined spaces"> </code><code class="plain">sum += A[i];</code></div><div class="line number15 index14 alt2"><code class="undefined spaces"> </code><code class="plain">}</code></div><div class="line number16 index15 alt1"><code class="undefined spaces"> </code> </div><div class="line number17 index16 alt2"><code class="undefined spaces"> </code><code class="comments">// Check if B's element are there in set</code></div><div class="line number18 index17 alt1"><code class="undefined spaces"> </code><code class="comments">// if exist then remove current element from</code></div><div class="line number19 index18 alt2"><code class="undefined spaces"> </code><code class="comments">// set, otherwise add current element into sum</code></div><div class="line number20 index19 alt1"><code class="undefined spaces"> </code><code class="keyword">for</code> <code class="plain">(let i = 0; i < n; i++) {</code></div><div class="line number21 index20 alt2"><code class="undefined spaces"> </code><code class="keyword">if</code> <code class="plain">(!st.has(B[i])) {</code></div><div class="line number22 index21 alt1"><code class="undefined spaces"> </code><code class="plain">sum += B[i];</code></div><div class="line number23 index22 alt2"><code class="undefined spaces"> </code><code class="plain">}</code></div><div class="line number24 index23 alt1"><code class="undefined spaces"> </code><code class="keyword">else</code> <code class="plain">{</code></div><div class="line number25 index24 alt2"><code class="undefined spaces"> </code><code class="plain">sum -= B[i];</code></div><div class="line number26 index25 alt1"><code class="undefined spaces"> </code><code class="plain">}</code></div><div class="line number27 index26 alt2"><code class="undefined spaces"> </code><code class="plain">}</code></div><div class="line number28 index27 alt1"> </div><div class="line number29 index28 alt2"><code class="undefined spaces"> </code><code class="comments">// Finally, return sum</code></div><div class="line number30 index29 alt1"><code class="undefined spaces"> </code><code class="keyword">return</code> <code class="plain">sum;</code></div><div class="line number31 index30 alt2"><code class="plain">}</code></div><div class="line number32 index31 alt1"> </div><div class="line number33 index32 alt2"><code class="comments">// Driver code</code></div><div class="line number34 index33 alt1"><code class="undefined spaces"> </code><code class="plain">let A = [ 5, 4, 9, 2, 3 ];</code></div><div class="line number35 index34 alt2"><code class="undefined spaces"> </code><code class="plain">let B = [ 2, 8, 7, 6, 3 ];</code></div><div class="line number36 index35 alt1"> </div><div class="line number37 index36 alt2"><code class="undefined spaces"> </code><code class="comments">// size of array</code></div><div class="line number38 index37 alt1"><code class="undefined spaces"> </code><code class="plain">let n = A.length;</code></div><div class="line number39 index38 alt2"> </div><div class="line number40 index39 alt1"><code class="undefined spaces"> </code><code class="comments">// function call</code></div><div class="line number41 index40 alt2"><code class="undefined spaces"> </code><code class="plain">document.write(findSum(A, B, n));</code></div></div></td></tr></tbody></table></div> |
39
Time Complexity: O(n*log n)
Auxiliary Space: O(n)
Contact Us