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!

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.

in this case if you are only comparing 'corresponding' elements then only one loop is required...

Maybe I used the wrong term. I want to check whether both array contain the same elements.

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.)

Is there a way to do it without sorting the arrays?

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.

Or you can use std::map to count how many times values occur in either array and then compare the maps.

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;
	
}

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.

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..

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.

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.

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.

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;
}