Need Help finding different values in 2 arrays

I need to find the difference between 2 arrays and store them in a 3rd array. I am having trouble account for repeat values in each of the first 2 arrays:
i.e.
array1 = 1 1 1 2 2
array2 = 2 1 2 1 2
differenceArray should be: 1 2

I have written the code below but when using the values above, I am getting the differenceArray holding 0 values. I know this is wrong, but everything I have tried hasn't worked either. I also had to find the intersection of these 2 arrays but simply doing the opposite didn't give me the right answers either.

Any help is much appreciated!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
  #include "ArrayBag.h"
#include <cstddef>

template<class ItemType>
ArrayBag<ItemType>::ArrayBag(): itemCount(0), maxItems(DEFAULT_CAPACITY)
{
}  // end default constructor

template<class ItemType>
int ArrayBag<ItemType>::getCurrentSize() const
{
	return itemCount;
}  // end getCurrentSize

template<class ItemType>
bool ArrayBag<ItemType>::isEmpty() const
{
	return itemCount == 0;
}  // end isEmpty

template<class ItemType>
bool ArrayBag<ItemType>::add(const ItemType& newEntry)
{
	bool hasRoomToAdd = (itemCount < maxItems);
	if (hasRoomToAdd)
	{
		items[itemCount] = newEntry;
		itemCount++;
	}  // end if
    
	return hasRoomToAdd;
}  // end add

/*
// STUB
 template<class ItemType>
 bool ArrayBag<ItemType>::remove(const ItemType& anEntry)
 {
    return false; // STUB
 }  // end remove
*/   
 
template<class ItemType>
bool ArrayBag<ItemType>::remove(const ItemType& anEntry)
{
   int locatedIndex = getIndexOf(anEntry);
	bool canRemoveItem = !isEmpty() && (locatedIndex > -1);
	if (canRemoveItem)
	{
		itemCount--;
		items[locatedIndex] = items[itemCount];
	}  // end if
    
	return canRemoveItem;
}  // end remove

/*
 // STUB
 template<class ItemType>
 void ArrayBag<ItemType>::clear()
 {
    // STUB
 }  // end clear
*/

template<class ItemType>
void ArrayBag<ItemType>::clear()
{
	itemCount = 0;
}  // end clear

template<class ItemType>
int ArrayBag<ItemType>::getFrequencyOf(const ItemType& anEntry) const
{
   int frequency = 0;
   int curIndex = 0;       // Current array index
   while (curIndex < itemCount)
   {
      if (items[curIndex] == anEntry)
      {
         frequency++;
      }  // end if
      
      curIndex++;          // Increment to next entry
   }  // end while
   
   return frequency;
}  // end getFrequencyOf
/*
template<class ItemType>
bool ArrayBag<ItemType>::contains(const ItemType& anEntry) const
{
	return getIndexOf(anEntry) > -1;
}  // end contains
**/

template<class ItemType>
bool ArrayBag<ItemType>::contains(const ItemType& target) const 
{
   return getFrequencyOf(target) > 0;
}  // end contains

/* ALTERNATE 2: Second version 
template<class ItemType>
bool ArrayBag<ItemType>::contains(const ItemType& anEntry) const
{
   bool found = false;
   int curIndex = 0;        // Current array index
   while (!found && (curIndex < itemCount))
   {
      if (anEntry == items[curIndex])
      {
         found = true;
      } // end if
      
      curIndex++;           // Increment to next entry
   }  // end while   
   
   return found;
}  // end contains
*/

template<class ItemType>
std::vector<ItemType> ArrayBag<ItemType>::toVector() const
{
   std::vector<ItemType> bagContents;
	for (int i = 0; i < itemCount; i++)
		bagContents.push_back(items[i]);
      
   return bagContents;
}  // end toVector

// private
template<class ItemType>
int ArrayBag<ItemType>::getIndexOf(const ItemType& target) const
{
	bool found = false;
   int result = -1;
   int searchIndex = 0;
   
   // If the bag is empty, itemCount is zero, so loop is skipped
   while (!found && (searchIndex < itemCount))
   {
      if (items[searchIndex] == target)
      {
         found = true;
         result = searchIndex;
      } 
      else
      {
         searchIndex++;
      }  // end if
   }  // end while
   
   return result;
}  // end getIndexOf

template<class ItemType>
ArrayBag<ItemType> ArrayBag<ItemType>::bagUnion(const ArrayBag<ItemType> &otherBag) const
{
	ArrayBag<ItemType> unionBag;
	
	
	for(int i = 0; i < getCurrentSize(); i++)
	{
		unionBag.add(items[i]);
	}
	
	
	for(int j = 0; j < otherBag.getCurrentSize(); j++)
	{
		unionBag.add(otherBag.items[j]);
	}
	
	return unionBag;
}	// end bagUnion



template<class ItemType>
ArrayBag<ItemType> ArrayBag<ItemType>::bagIntersection(const ArrayBag<ItemType> &otherBag) const
{
	ArrayBag<ItemType> intersectBag;
	
	int freq;
	int freq2;
	int minFreq;
	
	for(int i = 0; i < getCurrentSize(); i++)
	{
		if(otherBag.contains(items[i]))	
		{
			if(!intersectBag.contains(items[i]))
			{
				freq = getFrequencyOf(items[i]);	
				freq2 = getFrequencyOf(otherBag.items[i]);	
				if(freq < freq2)
				{
					minFreq = freq;
				}
				else
				{
					minFreq = freq2;
				}
				for(int j = 0; j < minFreq; j++)
				{
					intersectBag.add(items[i]);
				}
			}
		}
	}
	return intersectBag;
	
}	// end bagIntersection



template<class ItemType>
ArrayBag<ItemType> ArrayBag<ItemType>::bagDifference(const ArrayBag<ItemType> &otherBag) const
{
	ArrayBag<ItemType> differenceBag;
	for(int i = 0; i < getCurrentSize(); i++)
	{
		if(!otherBag.contains(items[i]))
		{
			differenceBag.add(items[i]);
		}
		
	}
	
	
	return differenceBag;
}//end of bagDifference 


Also if anyone wants to verify my bagIntersection method too that would be great.

Thanks!
Last edited on
Sorry, but your code is too complicated for me to follow. However, to find intersection and difference of two vectors you can use the following - method will probably apply to your code ... if I could follow that.

Fundamentally, just keep parallel bool arrays to indicate which elements have been included in the intersection.

To get the difference you effectively have to find the intersection ... so you might as well do both together anyway.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <vector>
#include <string>
using namespace std;

//======================================================================

template <class T> void myCompare( vector<T> A, vector<T> B, vector<T> &intersection, vector<T> &difference )
{
   intersection.clear();
   difference.clear();

   vector<bool> usedA( A.size(), false );        // keep tabs on which elements of A and B have been used in intersection
   vector<bool> usedB( B.size(), false );

   for ( int i = 0; i < A.size(); i++ )
   {
      for ( int j = 0; j < B.size(); j++ )
      {
         if ( !usedB[j] && B[j] == A[i] )        // found a match: stick it in intersection, and mark both A and B elements
         {
            intersection.push_back( A[i] );
            usedA[i] = true;
            usedB[j] = true;
            break;                               // breaks out of the search in B
         }
      }
   }

   for ( int i = 0; i < A.size(); i++ ) if ( !usedA[i] ) difference.push_back( A[i] );
   for ( int j = 0; j < B.size(); j++ ) if ( !usedB[j] ) difference.push_back( B[j] );
}

//======================================================================

template <class T> void write( string s, vector<T> A )
{
   cout << s;
   for ( T x : A ) cout << x << " ";
   cout << '\n';

}

//======================================================================

int main()
{
   vector<int> A = { 1, 1, 1, 2, 2 };
   vector<int> B = { 2, 1, 2, 1, 2 };
   vector<int> intersection, difference;

   myCompare( A, B, intersection, difference );
   write( "Intersection: ", intersection );
   write( "Difference:   ", difference   );
}


Intersection: 1 1 2 2 
Difference:   1 2 
Sorry, forgot to mention.... cannot use Vectors in this exercise.
Indeed. Well, you are using them on line 126 of your program.

Anyway, you can use whatever type of container or array you like: ArrayBags or whatever. The sample program uses vectors for convenience: the method would work with other types of storage.
Last edited on
Topic archived. No new replies allowed.