Reputation: 481
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
Reputation: 8215
Here's a solution that can be implemented with O(n) complexity:
Upvotes: 5
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