Non-overlapping sum of two sets

Difficulty Level Easy
Frequently asked in Accolite Amazon Hike Kuliza Pinterest Snapdeal Synopsys Teradata
Array HashingViews 2420

Problem Statement

The problem “Non-overlapping sum of two sets” states that you are given two arrays as input values as arrA[] and arrB[] of the same size n. Also, both of the arrays have distinct elements individually and some common elements. Your task is to find out the total sum of all the non-common elements.

Example

arrA[] = {1,3,4,5,2}
arrB[] = {2,4,6,7,8}
30

Explanation

Distinct elements in the above set of the array are 1, 3, 5, 6, 7, and 8.

Total Sum is = 1+ 3 + 5 + 6 + 7 +8 = 30.

Non-overlapping sum of two sets

 

arrA[]={1,3,4,5,2}
arrB[]={3,4,1,5,7}
9

Explanation

All elements are common so the output will be 0.

Algorithm

  1. Declare a map.
  2. Traverse the array while i < n ( length of the array ).
    1. Count and store the frequencies of both of the array’s elements into the map.
  3. Set totalSum to 0.
  4. Traverse the map.
    1. Check if the map having the element’s value equal to 1.
      1. If true, then keep adding all the elements into the totalSum.
  5. Return totalSum.

 Explanation

We have given two input arrays in which some of the elements are common. The problem statement asks to find out the total sum of all of the elements of both of the arrays which are uncommon. For this, we are going to use hashing. Hashmap works with key and values, it will have keys and the value is associated with the key. So it works together. We will declare a hashmap and in a single map, we are going to store elements of both of the arrays into the map with their frequencies.

Example

Let us consider an example: arrA[]={1,3,4,5,2}, arrB[]={2,4,6,7,8}

Since both of the arrays are of the same size n. While traversing both of the arrays we just need to traverse one time and in that, we will be done with the elements and frequencies. After that our map will have the following values.

map :{1:1, 2:2, 3:1, 4:2, 5:1, 6:1, 7:1, 8:1}.

After setting the variable totalSum to 0, we need to traverse the map to get the sum of all non-common elements. We will check the condition if any element has the frequency, that is 1, we will just pick that element and add that element and totalSum and store into totalSum.

totalSum=0,

  • Map’s first element ‘1’ has 1 frequency and add it to totalSum => totalSum + key = 0 +1 = 1.
  • The Map’s second element ‘2’ has frequency 2 so we will not be taking that key because it is common in both of the arrays.
  • Map’s first element ‘3’ has 1 frequency and add it to totalSum => totalSum + key = 1 +3 = 4.
  • The Map’s second element ‘4’ has frequency 2 so we will not be taking that key because it is common in both of the arrays.
  • Map’s first element ‘5’ has 1 frequency, we add it to totalSum => totalSum + key = 4 +5 = 9.

Similarly we will be adding 6, 7 and 8 in totalSum because all have the value 1 as a frequency. So it will become 1+ 3 + 5 + 6 + 7 +8 = 30.

Output: 30

Code

Implementation in C++ for Non-overlapping sum of two sets

#include <unordered_map>
#include<iostream>

using namespace std;

int findSum(int arrA[], int arrB[], int n)
{
    unordered_map<int, int> map;
    for (int i = 0; i < n; i++)
    {
        map[arrA[i]]++;
        map[arrB[i]]++;
    }
    int totalSum = 0;
    for (auto sel: map)
        if (sel.second == 1)
            totalSum += sel.first;

    return totalSum;
}
int main()
{
    int arrA[] = { 5, 1, 10, 4, 7 };
    int arrB[] = { 1, 6, 7, 8, 2 };
    int l = sizeof(arrA) / sizeof(arrA[0]);
    cout << findSum(arrA, arrB, l);
    return 0;
}

35

Implementation in Java for Non-overlapping sum of two sets

import java.util.HashMap;
import java.util.Map;

class nonOverlappingSum
{
    public static int findSum(int[] A, int[] B, int n)
    {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++)
        {
            if (map.containsKey(A[i]))
                map.put(A[i], map.get(A[i]) + 1);
            else
                map.put(A[i], 1);

            if (map.containsKey(B[i]))
                map.put(B[i], map.get(B[i]) + 1);
            else
                map.put(B[i], 1);
        }
        int totalSum = 0;
        for (Map.Entry entry : map.entrySet())
        {
            if (Integer.parseInt((entry.getValue()).toString()) == 1)
                totalSum += Integer.parseInt((entry.getKey()).toString());
        }
        return totalSum;

    }
    public static void main(String args[])
    {
        int arrA[] = { 5, 1, 10, 4, 7 };
        int arrB[] = { 1, 6, 7, 8, 2 };
        int l = arrA.length;
        System.out.println(findSum(arrA, arrB, l));
    }
}

35

Complexity Analysis

Time Complexity

O(n) where “n” is the length of the array. Because we have used a hashmap all the operations of searching, deletion and updation are being done in O(1) time complexity. Thus we were able to achieve linear time complexity.

Space Complexity

O(n) where “n” is the length of the array. Space is required to store the elements of both the arrays into map.

Translate »