Symmetrical Difference

[FreeSocks]

Hello guys!

So i'm trying to write a code where it checks 2 arrays that contain integers either positive or nagative ones. After that it should return the numbers that are seen either in the First array or the Second array. After that the result needs to be sorted from the lowest to the highest.

Example input: (4 and 3 are how much numbers to put in those 2 arrays)

4 3
8 12 9 1
8 10 9

Example output:
1 10 12

The code currently i'm using, adds a '0' at the start because the arrays are not the same size but it checkes it anyway. The idea is that the arrays don't have to be the same size. So if one array is 10 the other can be 3.

 #include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#define MAXN 1000000
using namespace std;

int a[MAXN], b[MAXN],n,m;
vector<int> v;


int main() {
    int i , j;
    cin >> n >> m;
    for(i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    for( i = 0; i < m; i++)
    {
        cin >> b[i];
    }
    
    for(i = 0; i < n ; i++)
    {
        
            if(a[i] != b[i])
            {
                v.push_back(a[i]);
                v.push_back(b[i]);
            }
            
           
    }

    sort(v.begin(), v.end());
    
    for(auto c : v)
    {
        cout << c << " ";
    }
    
    
    return 0;
}

I'm not sure how to make it work exactly.
Any help is appreciated.

[lastchance]

You are supposed to compare each element of a[] with ALL the elements of b[], and vice versa. At present you are only comparing elements with the same corresponding index and, if m < n, will read from non-initialised data.

If you are intending to do it by brute force you will need to replace lines 28 to 32 by a loop through all m elements of b[] to find which elements of a[] are not in b[]. Then you will need a second set of nested loops to find which elements of b[] are not in a[].

If you are not intending to it by brute force, but instead use the STL algorithms, then dump your two arrays into sets (which will also sort them and remove duplicates) and then use std:set_symmetric_difference:
http://www.cplusplus.com/reference/algorithm/set_symmetric_difference/

[FreeSocks]

@lastchange

i actually also tried that.

set<int> s1,s2;
set<int> result;


int main() {
    int i , j;
    cin >> n >> m;
    for(i = 0; i < n; i++)
    {
        cin >> j;
        s1.insert(j);
    }
    for( i = 0; i < m; i++)
    {
        cin >> j;
        s2.insert(j);
    }
    

set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(),
    inserter(result, result.end()));
    
    for(auto c : result)
    {
        cout << c << " "; 
    }
    
    return 0;
}

But in this case i don't get the number 10 , if i run the example input.
It would just give me 1 and 12.

Also someone told me to try with a merge or mergeSort algorithm. But i'm not sure how to apply that here and if its going to be logical. Aslo the idea behind this is that eventuallno the N can be a number up to 1 000 000.

Edit: Not only that N and M could go up to 1000000 but also i need to make sure this code runs fast enough. At that is the point of the exercise im trying to solve.

[MikeStgt]

how to make it work exactly

First, make your plan as exactly as necessary afore coding, otherwise... you know it.

After that it should return the numbers that are seen either in the First array or the Second array.

In other words, compare the two arrays positional (with the same index), if different keep both numbers for the result. The shorter array is padded with 0 at the end to match the size of the longer array; those 'filler-zeros' are omitted from the result.
That is what I concluded from your example:

a = {8 12 9 1}
b = {8 10 9}
R = {1 10 12} // result (sorted in 3rd step)

I suggest following change/additions:

    for(i = 0; i < (m<n?m:n) ; i++)
    {
            if(a[i] != b[i])
            {
                v.push_back(a[i]);
                v.push_back(b[i]);
            }
    }
    if (m<n)
    {
        for(i = m; i < n; i++)
            v.push_back(a[i]);
    }
    else if (n<m)
    {
        for(i = n; i < m; i++)
            v.push_back(b[i]);
    }

[lastchance]

FreeSocks wrote:

i actually also tried that.

No you didn't. You need to use
std::set_symmetric_difference
NOT
std::set_difference

Try this:

#include <iostream>
#include <set>
#include <algorithm>
using namespace std;


int main() {
    int i , j, m, n;       // m, n required
    set<int> s1,s2;        // Make local, not global, variables
    set<int> result;

    cin >> n >> m;
    for(i = 0; i < n; i++)
    {
        cin >> j;
        s1.insert(j);
    }
    for( i = 0; i < m; i++)
    {
        cin >> j;
        s2.insert(j);
    }
    
    set_symmetric_difference( s1.begin(), s1.end(), s2.begin(), s2.end(), inserter(result, result.end()) );

    for ( auto c : result ) cout << c << " "; 
    cout << '\n';
}

1 10 12 

[salem c]

    for(i = 0; i < n ; i++)
    {
            if(a[i] != b[i])
            {
                v.push_back(a[i]);
                v.push_back(b[i]);
            }
    }

1. If m != n, then either you're missing out on testing some b[i], or you're accessing b[i] which didn't come from the file.

2. You're assuming that the two arrays are perfectly aligned.

3 3
12 9 1
8 10 9

By your logic, 9 would be added twice, because it occurs in a different position in each array.