1

I came across this problem:

Given two arrays of numbers, find if each of the two arrays have the same set of integers. Suggest an algorithm which can run faster than N * log(N) without extra space.

Here is the link

find-if-two-arrays-contain-the-same-set-of-integers

algorithm-to-tell-if-two-arrays-have-identical-members

But after reading all answer from above mentioned links, I didn't find this simple answer which I came across, Here it is....

int main(){
    int a[] = {1,5,5,7,5,6,6};
    int b[] = {1,6,6,5,7,5,9};

    int i = 0;
    int size = 0;
    int xor_ab = a[0]^b[0];
    int sumDiff_ab = (a[0] - b[0]);;

    if(sizeof(a)/sizeof(a[0]) == sizeof(b)/sizeof(b[0])){
        size = sizeof(a)/sizeof(a[0]);
    }else{
        printf("not identical : array size differ");
        return 0;
    }

    for(i=1; i < size ; ++i){
        xor_ab = xor_ab ^ a[i] ^ b[i];
        sumDiff_ab += (a[i] - b[i]);
    }
    if(xor_ab == 0 && sumDiff_ab == 0){
        printf("identical");
    }else{
        printf("not identical");
    }
    return 0;
}

Now I want to know, whether my solution will work for all use cases or not. If not, Please let me know such use cases.

[EDIT]

Please consider all numbers are +ve in array.

[Accepted Answer]

I Accepted answer of @Boris Strandjev,

My solution won't work for cases like

{3,5}

{1,7}

Community
  • 1
  • 1
surender8388
  • 474
  • 3
  • 12

3 Answers3

4

Here is an example for which your algorithm will not work:

a[] = {3, 5};
b[] = {1, 7};

Two values calculated out of two arrays - too many different array sets will evaluate to the same two values. Such comparison for identity will never work (consider all collisions that will happen).

Boris Strandjev
  • 46,145
  • 15
  • 108
  • 135
0

Maybe that will not answer your question but what about using hashing functions to compare arrays ?

#include <stdio.h>
#include <stdlib.h>
#include <openssl/sha.h>
int main(){
    int a[] = {1,5,5,7,5,6,6};
    int b[] = {1,5,5,7,5,6,6};

    unsigned char hasha[SHA_DIGEST_LENGTH]; // == 20
    unsigned char hashb[SHA_DIGEST_LENGTH]; // == 20

    SHA1((char*) a , sizeof(a), hasha);
    SHA1((char*) b , sizeof(b), hashb);

    printf("Are arrays equals ? %d\n" , (strcmp(hasha,hashb)==0? 1:0));

    return 0;
}

and you can compile it with :

 gcc test.c -lssl -lcrypto -o test
Marc
  • 2,631
  • 1
  • 12
  • 13
  • Then why not using a library like openssl to do the hashing ? – Marc Sep 21 '13 at 11:35
  • 1
    My question was regarding the solution I mentioned above, If it will fails. i wanted know the use cases. Like mentioned by @Boris Strandjev – surender8388 Sep 21 '13 at 11:37
  • Ok, I just wanted to add a solution that was using a library to handle the hard work. But I know I did not answer your question. – Marc Sep 21 '13 at 11:41
  • @KarolyHorvath I agree only because, for this particular case, this answer likely would've been better suited as an answer to one of the questions linked in the question. [Alternate ways to solve the problem are usually OK](http://meta.stackexchange.com/a/179567/206447). – Bernhard Barker Sep 21 '13 at 17:46
0

This works for limited sizes of a[] and b[] and limited ranges of the values in a[] and b[] :

#include <stdio.h>

unsigned primes[] = {1,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71
                ,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149 };

int main(void)
{
unsigned a[] = {1,5,5,7,5,6,6};

#if SHOULD_BE_EQUAL
unsigned b[] = {1,5,5,6,7,5,6};
#else
unsigned b[] = {1,6,6,5,7,5,9};
#endif

#define COUNTOF(x) (sizeof x / sizeof x[0])

unsigned pa, pb, idx;

for (pa=1,idx=0 ; idx < COUNTOF(a); idx++) pa *= primes[a[idx]];
for (pb=1,idx=0 ; idx < COUNTOF(b); idx++) pb *= primes[b[idx]];

printf("A[] and b[] are %s equal\n", (pa==pb) ? "completely" : "not" );

return 0;
}
wildplasser
  • 43,142
  • 8
  • 66
  • 109