brute force approach for union of two array

Question

I wanted to apply brute force to find the union of two arrays and theoretically it should works but for some reason only first array goes into 3rd array(3rd array is for storing elements form array 1 and array2) and size of 3rd array is getting increased from 8 to 12

//find the union of two arrays
#include<iostream>
#include<vector>
using namespace std;

void uniarr(vector<int> &arr1, vector<int> &arr2)
{
    int n=arr1.size();
    int m=arr2.size();
    vector<int> arr3(n+m);
     cout<<" arr "<<arr3.size()<<endl;
    int count=1;
   
    for (int i = 0; i < n; i++)
    {   count=1;
  
        for (int  j = 0; j < arr2.size(); j++)
        {
            if(arr1[i]==arr2[j])
            {   
                if(count==1)
                 {
                    arr3.push_back(arr1[i]);
                    count++;
                 }
                arr2.erase(arr2.begin()+j);
                j=j-1;
            }   
        }
        if(count==1)
        {
            arr3.push_back(arr1[i]);
        }
    }
    cout<<" arr "<<arr3.size()<<endl;

for (int i = 0; i < arr3.size(); i++)
{
    cout<<" "<<arr3.at(i);
}

}
int main()
{   
    system("cls");
    vector<int> arr1={3,1,4,6};
    vector<int> arr2={1,2,5,4};

    uniarr(arr1,arr2);
    return 0;
}

`vector arr3(n+m);` is already setting the size to `n+m` and each `push_back` adds1 to the size. You should use arr3.`reserve(n+m)` instead. This will make the **capacity** `n+m`, and each `push_back` will increase the size by 1. See here: https://stackoverflow.com/questions/6296945/size-vs-capacity-of-a-vector. — wohlstad, Aug 15 '22 at 09:48
*"for some reason only first array goes into 3rd array"* -- that is strange. Could you point out the line that is supposed to add an element from `arr2` to `arr3`? — JaMiT, Aug 15 '22 at 09:53
Also everything from `arr1` goes into `arr3`. You should just copy that. And then copy all the elements from `arr2` that are not in `arr1` without altering `arr2`. That would get your algorithm from `O(n^3)` to at least `O(n^2)`. Modifying the input is not nice. You should take the input as `const vector &`. Overall `vector` is the wrong data structure for this, you should be using `set` or `unordered_set`. — Goswin von Brederlow, Aug 15 '22 at 15:22
yes i already know the optimal approach with unordered_set but i wanted to apply brute force also why its O(n^3)?? i guess its's O(n^2) only — sujal sharma, Aug 17 '22 at 05:40

Jarod42 · Accepted Answer · 2022-08-17T07:40:06.423

0

You have 2 issues:

First one, initialization of arr3

std::vector<int> arr3(n+m); // create a vector of SIZE n+m (with value 0)

it should be

std::vector<int> arr3;
arr3.reserve(std::min(n, m)); // "optimization" to avoid future allocation

Second one is your last
```
if(count==1)
{
    arr3.push_back(arr1[i]);
}
```
which add in arr3 element from arr1 not found in arr2. you should remove it.

Demo

edited Aug 17 '22 at 07:40

answered Aug 15 '22 at 10:42

Jarod42

203,559
14
181
302

score 0 · Answer 2 · answered Aug 17 '22 at 06:36

i needed to add additional for loop to add arr2 elements

reason : After adding elements from arr1 and deleting common elements form arr2 only unique elements would be left in arr2

also i needed to reserve the space for arr3 instead of allocating it with n+m

brute force approach for union of two array

2 Answers2