Reputation: 279
Scrambled Arrays in C
I'm new to C! So I get two equal length integer arrays as inputs and a len, which will always be equal to the len of the two arrays. I am supposed to verify if the integers in array A are equal to the integers in array B, order does not matter.
So for example, the following is ok:
A[:)] = {1,2,3}
B[:(] = {3,2,1}
But the following is not ok:
A[:)] = {1,1,1}
B[:(] = {1,2,3}
This is my code below with a sample test I put in main.c. However, my code fails to produce the right answer. But I am not sure why and I was wondering if someone could help point out where I am going wrong. Thanks in advance!
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
//flag = 1 means the two arrays are equal, or empty
//flag = 0 means that the two arrays are not equal
int scrambled( int a[], int b[], int len)
{
int i = 0;
int j = 0;
int flag = 0;
if (len == 0)
{
return 1;
}
for(i = 0; i < len; i++)
{
flag = 0;
for( j = 0; j < len; j++)
{
if( a[i] == b[j])
{
flag = 1;
}
}
if(flag == 0)
{
printf("Number not found\n");
return flag;
}
}
printf("Here is flag: %d\n", flag);
return flag;
}
int main()
{
int array[100] = {1,1,1};
int array2[100] = {1,2,3} ;
int len = 3;
scrambled(array,array2,len);
}
Upvotes: 1
Views: 2022
Answers (6)
Reputation: 4317
As mentioned by others, the problem with your code is that you were not doing an equality test, but, really, an inclusion test.
Please note, however, that even repeating the comparison with the arrays interchanged yields wrong results if you bother about repeated elements. E.g., try with {1,1,2} and {2,2,1}.
Here is a quick-and-dirty (yet mildly efficient) solution.
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
//flag = 1 means the two arrays are equal, or empty
//flag = 0 means that the two arrays are not equal
int scrambled(int a[], int b[], int len)
{
int i;
int j;
int flag;
if (len == 0)
{
return 1;
}
for(i = 0; i < len; i++)
{
flag = 0;
for(j = i; j < len; j++) // start with j = i
{
if(a[i] == b[j])
{
// we got a match, hence forget about b[j]
b[j] = b[i];
// one match is enough for the current iteration
flag = 1;
break;
}
}
if(flag == 0)
{
printf("Number not found\n");
return flag;
}
}
printf("Here is flag: %d\n", flag);
return flag;
}
int main()
{
int array[100] = {1,1,1};
int array2[100] = {1,2,3} ;
int len = 3;
scrambled(array,array2,len);
}
Upvotes: 1
Reputation: 16406
Using ideas of BLUEPIXY and user3435489:
#include <stdbool.h>
#include <string.h>
#include <stdio.h>
bool match_scrambled( int a[], int b[], int len)
{
if (len == 0) return true;
int bx[len], nbx = len;
memcpy(bx, b, sizeof bx);
for (int i = 0; i < len; ++i)
for (int j = 0;; ++j)
{
if (j == nbx)
return false;
if( a[i] == bx[j])
{
bx[j] = bx[--nbx];
break;
}
}
return true;
}
int main()
{
int array[] = {1,1,1};
int array2[] = {1,2,3};
if (!match_scrambled(array, array2, sizeof array / sizeof *array))
printf("no ");
printf("match\n");
return 0;
}
Upvotes: 0
Reputation: 40145
int scrambled( int a[], int b[], int len){
int i, j, flag;
char flags[len];
if (len == 0) return 1;
memset(flags, 0, len);
for(i = 0; i < len; ++i){
flag = 0;
for( j = 0; j < len; ++j){
if( a[i] == b[j] && flags[j]==0){
flags[j] = flag = 1;
break;
}
}
if(flag == 0)
return 0;
}
return 1;
}
Upvotes: 2
Reputation: 122
Your code only checks if every number in a[] exists in b[] and not the other way around. a[] only contains 1's --> {1,1,1}. It checks all three 1's against b[] and every time it finds the 1 in b[].
The code should also check if every number in b[] exists in a[]. If you add that, then your code is complete.
This works.. (note that bubble sort is slow for large arrays!)
#include <stdio.h>
static void bubble_sort_ints(int a[], int len)
{
int i, j, t;
for (i = 0; i < len - 1; i++) {
for (j = i + 1; j < len; j++) {
if (a[i] > a[j]) {
t = a[i];
a[i] = a[j];
a[j] = t;
}
}
}
}
static int scrambled(int a[], int b[], int len)
{
bubble_sort_ints(a, len);
bubble_sort_ints(b, len);
int i;
for (i = 0; i < len; i++) {
if (a[i] != b[i]) {
return 0;
}
}
return 1;
}
int main(void)
{
int a[5] = {1, 2, 2, 2, 3};
int b[5] = {1, 1, 2, 3, 3};
printf("%s\n", scrambled(a, b, 5) ? "ok" : "not ok");
return 0;
}
Upvotes: 5
Reputation: 9522
Your code is not correct. Your code detects if all the elements of array1 are in array 2 but not the other way around. Try calling
scrambled(array2,array,len);
and you'll see.
Upvotes: 0
Reputation: 10486
What you're code is actually doing is telling you if every value in first array can be found in second array. I suggest you to run the function 2 times by swapping said arrays and compare the result :
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
//flag = 1 means the two arrays are equal, or empty
//flag = 0 means that the two arrays are not equal
int scrambled( int a[], int b[], int len)
{
int i = 0;
int j = 0;
int flag = 0;
if (len == 0)
{
return 1;
}
for(i = 0; i < len; i++)
{
flag = 0;
for( j = 0; j < len; j++)
{
if( a[i] == b[j])
{
flag = 1;
}
}
if (flag == 0)
return flag;
}
return flag;
}
int main()
{
int array[100] = {1,1,1};
int array2[100] = {1,2,3} ;
int len = 3;
if (scrambled(array,array2,len) && scrambled(array2,array,len))
printf("Equal\n");
else
printf("Not equal\n");
}
Output is Equal for {1,3,2} ; {1,2,3} and Not equal for {1,1,1} ; {1,2,3}.
Upvotes: 0