Scrambled array in c

Question

I’m doing a scrambled array where I have to compare two arrays to see if their contents match. I have looked at other scrambled array solutions but for my assignment I cannot change the arrays in any way (no sorting).

#include <stdio.h>
int scrambled(unsigned int a[], unsigned int b[], unsigned int len){

    int firstCheck = 0;
    int secondCheck = 0;
    int i = 0;
    int j = 0;

    for(i=0; i < len; i++){
        firstCheck = 0;

        for(j=0; j< len; j++){
            if(a[i] == b[j]){
                firstCheck = 1;

            }

        }

        if(firstCheck != 1){
            firstCheck = 0;
            break;
        }
    }


    for(j=0; j < len; j++){
        secondCheck = 0;

        for(i=0; i< len; i++){
            if(b[j] == a[i]){
                secondCheck = 1;
            }

        }

        if(secondCheck != 1){
            secondCheck = 0;
            break;
        }
    }

    if(len == 0){
        return 1;
    }else if (firstCheck == 0 || secondCheck == 0){
        return 0;
    }else{
        return 1;
    }

}

I was given some array examples to test if the code works and all of them work. If the arrays are empty, it should return 1;. My code passed through all the tests but the grading program doesn’t accept my code. I am wondering if I am missing a crucial check?

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}

I do have a main code for testing, I’ll post it just in case.

#include <stdio.h>
#include <stdbool.h>

int scrambled (unsigned int a[], unsigned int b[], unsigned int len);
int main(){
    unsigned int a[5] = {1,2,3,4,5};
    unsigned int b[5] = {5,3,4,2,2};
    bool result;

    result = (scrambled(a,b,5));

    if(result == 1){
        printf("b is a scrambled version of a\n");
    }else{
        printf("b is NOT a scrambled version of a\n");
    }
    return 0;
}

Edit:

Thanks for all the replies! I'll try cleaning up my code and trying the methods mentioned (auxiliary arrays/helper function/return statements). I'll make sure to tag only one C next time as I learned they are very different. I'm glad to hear it isn't a logic problem, so perhaps I read the instructions wrong. Posted them below if anyone wants to look. (for #4 it says iff arrays, I assumed it was a typo, is it?)

1) Create a new file called scrambled.c, containing a single function that matches this declaration:

2) int scrambled( unsigned int a[], unsigned int b[], unsigned int len );

3) Arrays a and b are both of length len, and contain values in the range [0 99] inclusive, only.

4) The function scrambled() should return 1 iff arrays a and b contain the same values in any order, or 0 otherwise.

5) len can have any unsigned int value, including 0.

6) If len is 0 then scrambled() should return 1 (since the arrays have the same - empty - contents).

7) You must not change the contents of the arrays.

8) Use an algorithm that has run time linear in the array length n. Note that this means you can not sort the arrays since that can not be done in linear time..

Will update if I manage to figure this out!

Answer 1

In order to run in linear time, there's actually a clever way of coding the program. First, we create two arrays with 100 elements and initialize them to zero.

firstArray[100] = {0}; secondArray[100] = {0};

Then, you would go through the array and count how many times a number appeared in that index(adding one at that index to the counter array). This only works from 0-100, which is within the requirements. You would go through both arrays and have "counter arrays" for both.

For example, So like let’s say my firstArray is 1,3,3,...

My counterFirstArray will look like 1,0,2,0,0,...,0 (all the way to one hundred).

And my secondArray is 3,3,1,... The counterSecondArray will tell us how many times that number appears in the given array. This yields the same result as counterFirstArray (1,0,2,0,0...0 ) because we have gone through each array counting the index of each number and adding one to that index.

Then at the end you compare both arrays from the counter arrays!

Answer 2

Your code is no longer Big-O of N or O(N) linear time. Since you have two "for loops" in your code. The requirements state that you must run in linear time.

Answer 3

I don't see any logical error in your code. So unless you missed some rules stated in the assignment your code should pass the tests.

As stated in the comments, I'd suggest introducing a helper function in order to avoid two very similar code fragments:

#include <stdio.h>
#include <stdbool.h>

bool firstIsContainedInSecond(unsigned int a1[], unsigned int a2[], unsigned int len) {
    for(int i=0; i < len; i++){
        bool contained = false;
        for(int j=0; j< len; j++){
            if(a1[i] == a2[j]){
                contained = 1;
                break;
            }
        }
        if (!contained)
            return false;
    }
    return true;
}

int scrambled(unsigned int a[], unsigned int b[], unsigned int len){

    if(len == 0){
        return 1;
    } else if (! firstIsContainedInSecond(a, b, len)){
        return 0;
    } else if (! firstIsContainedInSecond(b, a, len)){
        return 0;
    }else{
        return 1;
    }
}