Find Non-overlapping sum of two sets in C++

In this tutorial, we will learn how to find out the Non-overlapping sum of two sets in C++.

This tutorial does not assume all the elements in a single array are different. It takes into account the cases when several elements in an array may be similar to each other in the same array but not present in the second array.

We will analyze the naive algorithm, and the efficient algorithms using Time complexity analysis and also, in the end, figure out how to code for it in C++ efficiently.

Find Non-overlapping sum even with repetitions in same array

Introduction to the problem:

We are given two sets both of length n. These sets contain integers that may be distinct from one another in the same array or repeated in the same array, or present in only one of the arrays and not in the other. Given any two sets, our goal is to find the sum of integers that are present in only one of the arrays, either the first or second array. Integers that are present in both the arrays simultaneously do not fall under the category “non overlapping”. Now that we have defined what we mean by non-overlapping, let us proceed to the crux of deciding which algorithm to use.

Naive Algorithm:

By intuition, we can see how we can solve this problem. The basic idea is to check if an element that is present in one of the arrays is present in the other. For this purpose, we need to traverse through the first array and for each element in the first array we need to check if it is present in the second array or not by going through the whole of the second list. This means that we will have a nested for loop which goes through the second array fully each time for every element in the first array. We can safely conclude that the Time complexity of this approach is O(n^2).

Efficient Algorithm:

We can do much better than the naive algorithm. To achieve a linear time complexity, we need to go through each array only once. We will make use of another concept here. The Mighty Hash Map. The Hash Map is always efficient because of it’s constant lookup time O(1). The idea is first to traverse through each array, and update an unordered map with the elements present in both the arrays and the number of times they appear as their value.

So if the arrays contain distinct elements in each array, then the element that appears in both the arrays will have a count of 2. We can then wade them off to select only the ones that have a single count. The problem with this method is that it ignores the case that there may be two same elements in the same array and not be present in the other array. In this case also, the count goes to 2. We can avoid this by using an improved but similar algorithm that takes care of this. The use of an unordered map increases space to O(n).

Improved Efficient Algorithm:

Instead of having the value of the unordered map as an int value we change it to an object of a class which can hold two values. Based on which of these two values holds the integer, we can decide if the element is present in the same array or in different arrays. We define a class with two member variables for this. We accordingly update the variable specific to which array they are present in. We see that we traverse through the array once which is O(n) and through the dictionary once which is again separately O(n). The total time complexity becomes O(n). The space complexity remains at O(n) from the previous method.

C++ program: Find Non-overlapping sum of two sets

#include<iostream>
#include<stdio.h>
#include <bits/stdc++.h> 
using namespace std; 
 

int calcNonOverlapSum(int array1[], int array2[], int n)
{ 
    class whichArray{
        public:
        int a=0;
        int b=0;
    };
    
    whichArray obj1;
    unordered_map<int, whichArray> countDict;     
    for (int i = 0; i < n; i++) { 
        countDict[array1[i]].a++; 
        countDict[array2[i]].b++; 
    } 
  
    int nonOverlapSum = 0; 
    for (auto j: countDict) {
        if (j.second.a >= 1 && j.second.b==0)
            nonOverlapSum += (j.first*j.second.a);
        if (j.second.a == 0 && j.second.b>=1)
            nonOverlapSum += (j.first*j.second.b);
    }
        
         
      
    return nonOverlapSum; 
} 

int main() 
{ 
    
    int n;
    cout<<"Enter the number of elements in the arrays"<<endl;
    cin>>n;
    int array1[n]; 
    int array2[n]; 
    cout<<"Enter the elements of array1 "<<endl;
    for(int i=0; i<n; i++){
        int ele;
        cin>>ele;
        array1[i]=ele;
    }
    cout<<"Enter the elements of array2 "<<endl;
    for(int j=0; j<n; j++){
        int ele1;
        cin>>ele1;
        array2[j]=ele1;
    }
    
    cout <<"The Non Overlapping sum is"<<" "<<calcNonOverlapSum(array1, array2, n);  
    return 0; 
} 
Output:

Enter the number of elements in the arrays

6

Enter the elements of array1

5 5 4 3 2 1

Enter the elements of array2

4 6 3 7 8 1

The Non Overlapping sum is 33

We can check this code by verifying the arrays ourselves. The nonoverlapping elements are: 5, 5, 2, 6, 7, 8. Their sum is 33.

Leave a Reply

Your email address will not be published. Required fields are marked *