Di Wang
Di Wang

Reputation: 481

Check 2 arrays if they have the same content, ignoring order, no sorting. What is the most efficient algorithm

Examples of arrays for which scrambled should return 1:

a = {10,15,20}, b = {10,15,20}
a = {99}, b = {99}
a = {1,2,3,4,5}, b = {5,3,4,2,1}
a = {}, b = {} (i.e. len = 0)
a = {2,1,3,4,5}, b = {1,2,4,3,5} 

Examples of arrays for which scrambled should return 0:

a = {1,1}, b = {1,2}
a = {10,15,20}, b = {10,15,21}
a = {1,2,3,4,5}, b = {5,3,4,2,2} 

My code in C is like this, but it is a O(N^2) not very efficient.

int scrambled( unsigned int a[], unsigned int b[], unsigned int len )
{
    int count1 = 0;
    int count2 = 0;

    for (int i=0; i< len; i++)
    {
        for (int j=0;j<len; j++)
        {
            if (a[i]==b[j])
            {
                count1++;
                break;
            }       
        }

        for (int j=0; j<len; j++)
        {
            if (b[i]==a[j])
            {
                count2++;
                break;
            }
        }
    }

    return (count1 == len && count2 == len );


}

Above code is flawed. Is there a linear solution for this?

Upvotes: 3

Views: 573

Answers (2)

Frank Puffer
Frank Puffer

Reputation: 8215

Here's a solution that can be implemented with O(n) complexity:

  1. Create a hash map for each array. The key is the array element. The value is the number of occurences.
  2. Iterate over the keys of the first hash map and check if the value is the same for both hash maps.
  3. If all values are the same, the arrays are equal.

Upvotes: 5

Di Wang
Di Wang

Reputation: 481

This is the fixed code.

# include <stdio.h>

int scrambled( unsigned int a[], unsigned int b[], unsigned int len )
{
    int count [99] = {0};
    for (int i=0; i < len; i++)
    {
        count [a[i]]++;
        count [b[i]]--;     
    }
    for (int i=0; i < 99; i++)
    {
        if (count[i]!=0){return 0;}
    }
    return 1;
}

Upvotes: 1

Related Questions