# Equality of 2 Arrays

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 03-04-2010
7heavens
Equality of 2 Arrays
Hi guys. I am having trouble with checking equality of 2 Arrays which have integers.. At first it sounded easy, but for some unknown reason, I'm finding it hard to code. I don't want to sort out the arrays first..

Code:

```int A[11]={1,7,5,7,4,3,5,2,1,9,8}; int B[11]={9,8,1,2,3,5,1,5,7,7,4}; for(int i=0;i<11;i++) {         for(int j=0;j<11;j++)         {                     if (A[i]==B[j])                                   return true;         } }```
I know this doesn't work.. Haha.. Can anyone give me some ideas on how to solve this. I thought this was supposed to be easy but I'm struggling!! Thanks!
• 03-04-2010
laserlight
Proposition: the two arrays are equal, where "equal" means that each corresponding element is equal. Simultaneously iterate over the arrays to find a counter example, i.e., corresponding elements that are not equal. If you cannot find such a counterexample, then you have proven the proposition to be true by exhaustive consideration of cases.
• 03-04-2010
rogster001
in this case if you are only comparing 'corresponding' elements then only one loop is required...
• 03-04-2010
7heavens
Maybe I used the wrong term. I want to check whether both array contain the same elements.
• 03-04-2010
laserlight
Quote:

Originally Posted by 7heavens
I want to check whether both array contain the same elements.

Sort, then it's business as usual. (Unless you want to remove duplicates, in which case you remove them after sorting as they would be clumped together, making them easier to detect.)
• 03-04-2010
7heavens
Is there a way to do it without sorting the arrays?
• 03-04-2010
laserlight
Of course. For example, you could iterate over one array and attempt to find a corresponding element in the other array. If no such element is found, you know the arrays are not equal.

You need to be careful though: what exactly do you mean by "both array contain the same elements"? For example, is an array that contains only one element, which has the value of 123, equal to an array containing two elements, both of which have the value of 123? They contain the same elements, but they are not of the same size.
• 03-04-2010
anon
Or you can use std::map to count how many times values occur in either array and then compare the maps.
• 03-04-2010
7heavens
Thank you for the prompt responses laserlight. What I meant by both array contain the same elements is that the size of both the array is the same and they contain the same elemenets but not necessarily in order. For example, int A[]={1,2,3} and int B[]={3,1,2} contains the same elements. Got the algorithm already. Here's my code. =)

Code:

```#include <iostream> #include <string> using namespace std; bool equality ( int A[], int B[],int size) {         for(int x=0; x<size; x++)         {                  bool alreadyPresent = false;                  for(int y=0; y<size; ++y)                 {                                        if(A[x] == B[y])                                 alreadyPresent =  true;                 }                 if (alreadyPresent==false)                         return false;         }         return true; } int main() {         int A[]={1,2,3,4,5};         int B[]={5,4,1,3,2};         cout << equality(A,B,5) <<endl;         }```
• 03-04-2010
_Mike
Your logic is flawed. You only test if the elements from A are present in B, not how many of each there are or if B has elements not present in A. Test your code with
Code:

```int A[]={1,1,1,1,2}; int B[]={1,2,2,2,2};```
Code:

```int A[]={1,1,1,1,1}; int B[]={1,2,3,4,5};```
Not equal, but your code says they are.
• 03-04-2010
7heavens
Haha.. Yeah. Was about to post about that. What can I do to the code to make it work? I don't want to sort.. :)
• 03-04-2010
hk_mp5kpdw
Use an STL multiset. Initialize two different multiset containers with the data from the arrays and then just return container1 == container2. That's like 2 or 3 lines of code.
• 03-04-2010
brewbuck
Quote:

Originally Posted by hk_mp5kpdw
Use an STL multiset. Initialize two different multiset containers with the data from the arrays and then just return container1 == container2. That's like 2 or 3 lines of code.

Even though this is easy from a coding perspective, it constructs a rather elaborate data structure in memory.
• 03-05-2010
grumpy
Quote:

Originally Posted by brewbuck
Even though this is easy from a coding perspective, it constructs a rather elaborate data structure in memory.

Indeed. It would be easier to create copies of both arrays. Then, working with the copies, sort and compare.
• 03-05-2010
7heavens
I finally figured it out! =) I wanted to do it without sorting.. I hope this time I'm correct. I spent quite a lot of time on this!! Tried the test cases Mike posted and other test cases.. If there's anything wrong, do let me know. Thank you for all the responses. Here is my code. It assumes that the array doesn't have -1 as an element.. I think the code is pretty self-explanatory..

Code:

```#include <iostream> #include <string> using namespace std; bool equality( int A[],int B[], int size) {         int *p=new int[size];         for (int i=0;i<size;i++)         {                 p[i]=B[i];         }         for(int i=0;i<size;i++)         {                 bool found=false;                 for(int j=0;j<size;j++)                 {                         if(A[i]==p[j])                         {                                 p[j]=-1;                                 found=true;                                 break;                         }                 }                 if (found==false)                         return found;         }         return true; } int main() { int A[]={1,1,1,2,1,1}; int B[]={1,1,2,1,1,1};         cout << equality(A,B,6)<<endl;         return 0; }```
Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last