wu :: forums
« wu :: forums - are two arrays equal ? »
Welcome, Guest. Please Login or Register.
Apr 29th, 2024, 7:02am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   cs (Moderators: william wu, Eigenray, Icarus, SMQ, ThudnBlunder, Grimbal, towr)
   are two arrays equal ?		 « Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: are two arrays equal ?  (Read 4410 times)
ravikumarv
Newbie
*





   


Gender: male
 Posts: 5
are two arrays equal ?  
« on: Nov 24th, 2011, 10:05pm »		 Quote Quote Modify Modify
There are two arrays.
 
int arr1[5] = { 3, 5, 2, 5, 2}
int arr2[5] = { 2, 3, 5, 5, 2}
 
The arrays will be called similar if they contain same number of elements equally(same elements). No hashing or sorting to be used.
 
My answer:
1.first condition is lengths should be equal
2.comparing elements as below
bool similar(int a[n], int b[m])
{
bool stop
int i,j
int skip=0;
for(i=0; i < n ;   i++)
{
stop=true
for(j=0; j < m-skip;j++)
{
if(a[i] == b[j])
{
c=b[j];
b[j]=b[m-skip-1]  // move last element to jth position
b[m-skip-1]=c;  // move current matched element to last
skip++;
stop=false;
}
}
if(stop) // true means current element of a is not in b
{
printf ("Not similar");
return false;
}
}
printf ("Similar");
return true;
}
 
I was asked efficient way than above
« Last Edit: Nov 24th, 2011, 11:02pm by ravikumarv » IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
 Posts: 13730
Re: are two arrays equal ?  
« Reply #1 on: Nov 26th, 2011, 11:18am »		 Quote Quote Modify Modify
You could use a (balanced) tree to count the number of occurrences of each element in both arrays. That would be O(n log n)
IP Logged
Wikipedia, Google, Mathworld, Integer sequence DB
krishnav
Newbie
*





   


Posts: 12
Re: are two arrays equal ?  
« Reply #2 on: Dec 24th, 2011, 12:47pm »		 Quote Quote Modify Modify
how about checking that sum of all numbers and product of all numbers of one array is equal to sum of all numbers and product of all numbers of the other array?
(if the arrays have negative elements, then we can add the abs val of the smallest # element to make all elements >=0). We could also eliminate 0's from the products and make sure # of 0's in both arrays is same.
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
 Posts: 13730
Re: are two arrays equal ?  
« Reply #3 on: Dec 24th, 2011, 1:35pm »		 Quote Quote Modify Modify
That wouldn't distinguish pairs of arrays such as [1,2,2,2,3], [4,6]
Also using a product becomes pretty inefficient as the number of elements in the arrays increase.
IP Logged
Wikipedia, Google, Mathworld, Integer sequence DB
krishnav
Newbie
*





   


Posts: 12
Re: are two arrays equal ?  
« Reply #4 on: Dec 24th, 2011, 7:12pm »		 Quote Quote Modify Modify
@towr : ofcourse we'ld check that the lengths of the arrays are same.
For inefficient products, we could pick a few large primes and just keep the mods.
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
 Posts: 13730
Re: are two arrays equal ?  
« Reply #5 on: Dec 25th, 2011, 2:32am »		 Quote Quote Modify Modify
It doesn't help to also check the length. You can have arrays that have the same length, same sum, same product and are still different. For example [2,2,2,2,2,5,12]  and [1,1,3,4,4,4,10]. It's not actually all that hard to construct them: take any two arrays with the same length and same product, then repeatedly add 2,2 to the one with the greater sum and 1,4 to the one with the lesser sum until the sums are equal. (And there are many other ways to do it.)
 
You lose information with each of those transformations (moreso if you do it modulo some large prime), so therefore at some point you must fail to distinguish two different arrays. You can use it to rule out many cases where two arrays are not similar, but you can't use it to confirm when they are similar.
(Also, it probably counts as hashing Tongue )
« Last Edit: Dec 25th, 2011, 2:34am by towr » IP Logged
Wikipedia, Google, Mathworld, Integer sequence DB
krishnav
Newbie
*





   


Posts: 12
Re: are two arrays equal ?  
« Reply #6 on: Dec 25th, 2011, 6:31pm »		 Quote Quote Modify Modify
the repeated addition of 2,2 & 1,4 to the two different arrays is a nice idea.  
 
how about if we compare the sum of the #'s and sum of squares of the #'s? Is there a case where they are same yet numbers are different (assuming all are > 0)
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
 Posts: 13730
Re: are two arrays equal ?  
« Reply #7 on: Dec 26th, 2011, 12:40am »		 Quote Quote Modify Modify
There should be infinitely many for the same reason as before: you lose so much information that some non-similar arrays must get the same hash.
 
The only puzzle is to find an example, but we can use pythagorean triples to construct some:
[ 7, 24, 17]
[ 8, 15, 25]
 
 
In general, we can take any two pythagorean triple, exchange the hypothenuses, and use [3,4,13] and [5,12,5] to make up the difference in sums.
For example
202+212 = 292 & 692+2602 =2692  
=>
[20, 21, 269]+24*[3,4,13] & [ 69, 260, 29]+24*[5,12,5]
 
 
Adding more to the mix (for example sum of cubes) won't help either; it will make it more difficult to find a hash-collision, but one will exist unless you have as many sums of powers as there are elements in the array.
« Last Edit: Dec 26th, 2011, 12:44am by towr » IP Logged
Wikipedia, Google, Mathworld, Integer sequence DB
amanchd
Newbie
*





   


Posts: 2
Re: are two arrays equal ?  
« Reply #8 on: Mar 8th, 2012, 9:12am »		 Quote Quote Modify Modify
I guess Taking XOR of both the arrays and comparing them can also be used with above checks mentioned....
IP Logged
amanchd
Newbie
*





   


Posts: 2
Re: are two arrays equal ?  
« Reply #9 on: Mar 8th, 2012, 9:23am »		 Quote Quote Modify Modify
Can go for comparison with GCD and LCM of both arrays  also.I guess .these many checks. are sufficient...although no proof
IP Logged
ashmish2
Newbie
*





   


Posts: 12
Re: are two arrays equal ?  
« Reply #10 on: Mar 22nd, 2012, 3:14am »		 Quote Quote Modify Modify
Assuming array to be array1 and array2  
 
bool checkArray(array1, array2) {
 
if(array1.length() != array2.length())
    return false;
BuildBST (array1); // (n log (n))
 
for i=0 to array2.length()    
   if(!searchBst(array2[i]))     //nlog(n)
  return false;
return true;
 
}
IP Logged
arun gupta
Newbie
*



hello friends :)

   


Gender: male
 Posts: 19
Re: are two arrays equal ?  
« Reply #11 on: Mar 26th, 2012, 1:57am »		 Quote Quote Modify Modify
Oh! i never think about this question?  Roll Eyes
IP Logged
tuxilogy
Newbie
*





   


Posts: 45
Re: are two arrays equal ?  
« Reply #12 on: Apr 14th, 2012, 8:41pm »		 Quote Quote Modify Modify
@ashmish
 
What if there are repetitions in the array then how you are constructing the BST
« Last Edit: Apr 14th, 2012, 8:42pm by tuxilogy » IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
 Posts: 7527
Re: are two arrays equal ?  
« Reply #13 on: Apr 16th, 2012, 7:51am »		 Quote Quote Modify Modify
You only need to replace searchBst by a procedure that also removes the item from the BST when it finds it.
IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board