wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> are two arrays equal ?
        
(Message started by: ravikumarv on Nov 24^th, 2011, 10:05pm)

Title: are two arrays equal ?
Post by ravikumarv on Nov 24^th, 2011, 10:05pm

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

Title: Re: are two arrays equal ?
Post by towr on Nov 26^th, 2011, 11:18am

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)

Title: Re: are two arrays equal ?
Post by krishnav on Dec 24^th, 2011, 12:47pm

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.

Title: Re: are two arrays equal ?
Post by towr on Dec 24^th, 2011, 1:35pm

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.

Title: Re: are two arrays equal ?
Post by krishnav on Dec 24^th, 2011, 7:12pm

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

Title: Re: are two arrays equal ?
Post by towr on Dec 25^th, 2011, 2:32am

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 :P )

Title: Re: are two arrays equal ?
Post by krishnav on Dec 25^th, 2011, 6:31pm

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)

Title: Re: are two arrays equal ?
Post by towr on Dec 26^th, 2011, 12:40am

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
20²+21² = 29² & 69²+260² =269²
=>
[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.

Title: Re: are two arrays equal ?
Post by amanchd on Mar 8^th, 2012, 9:12am

I guess Taking XOR of both the arrays and comparing them can also be used with above checks mentioned....

Title: Re: are two arrays equal ?
Post by amanchd on Mar 8^th, 2012, 9:23am

Can go for comparison with GCD and LCM of both arrays also.I guess .these many checks. are sufficient...although no proof

Title: Re: are two arrays equal ?
Post by ashmish2 on Mar 22^nd, 2012, 3:14am

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;

}

Title: Re: are two arrays equal ?
Post by arun gupta on Mar 26^th, 2012, 1:57am

Oh! i never think about this question? ::)

Title: Re: are two arrays equal ?
Post by tuxilogy on Apr 14^th, 2012, 8:41pm

@ashmish

What if there are repetitions in the array then how you are constructing the BST

Title: Re: are two arrays equal ?
Post by Grimbal on Apr 16^th, 2012, 7:51am

You only need to replace searchBst by a procedure that also removes the item from the BST when it finds it.