array search complexity problem

[vnbp8187]

find the commom numbers in two integer arrays with minimum code using c programming and explain its complexity....

[CommonTater]

Please do your own homework.

Make an attempt... get it as far along as you can... then If you get stuck post your code (In code tags please) and we'll see what we can do...

[Crosility]

Though CommonTater is correct.. noone will write it for you. (Or shouldn't)..

I suggest running a while loop, with x and y as the components. Y will increase till the end of the array. If there is a common number it'll say so. Then x increases by 1 when y is max, and set y back to 0.

It'll look all the way around, and should work. There's other methods. But that'll be basic, and no code overload.

[vnbp8187]

This is my code but i want it to be more short , "only 1 if loop" .and how can i caliculate the complexity of this program???please help me...


#include<stdio.h>
/* Function prints common of a1[] and a2[] */
int common(int a1[], int a2[], int m, int n) /* m is the size in a1[] n is the size in a2[] */
{
int i = 0, j = 0;
while(i < m && j < n)
{
if(a1[i] < a2[j])
i++;
else if(a2[j] < a1[i])
j++;
else /* if a1[i] == a2[j] */
{
printf(" %d ", a2[j++]);
i++;
}
}
}

/* program to test above function */
int main()
{
int a1[] = {1, 2, 4, 5, 6};
int a2[] = {2, 3, 5, 7};
int m = sizeof(a1)/sizeof(a1[0]);
int n = sizeof(a2)/sizeof(a2[0]);
common(a1, a2, m, n);
getchar();
return 0;
}

Output:2 5

[anduril462]

Here's your code with code tags and proper indentation (please do this yourself in the future).

#include<stdio.h>
/* Function prints common of a1[] and a2[] */
int common(int a1[], int a2[], int m, int n) /* m is the size in a1[] n is the size in a2[] */
{
    int i = 0, j = 0;
    while(i < m && j < n)
    {
        if(a1[i] < a2[j])
            i++;
        else if(a2[j] < a1[i])
            j++;
        else /* if a1[i] == a2[j] */
        {
            printf(" %d ", a2[j++]);
            i++;
        }
    }
}

/* program to test above function */
int main()
{
    int a1[] = {1, 2, 4, 5, 6};
    int a2[] = {2, 3, 5, 7};
    int m = sizeof(a1)/sizeof(a1[0]);
    int n = sizeof(a2)/sizeof(a2[0]);
    common(a1, a2, m, n);
    getchar();
    return 0;
}

Now, there's no such this as an 'if loop', but you can do this with one for/while loop, as you have shown, but only if the lists are sorted.

For complexity, read up on big O notation, then take a guess at how long your program takes to run. Hint, if you make the lists twice as long, how much longer will your program take to run? What if you make the lists 10 times as long?

[GReaper]

You figured out how to write this complex function and you can't optimize it or calculate its complexity? I then doubt that's your code at all. Therefore, there's no point at helping you!

[Adak]

It's not that complex - it's broken, actually.

Try these numbers to see why.

/* program to test above function */
int main()
{
int a1[] = {3,1,2, 4, 6, 5};
int a2[] = {2, 3, 5, 7};
int m = sizeof(a1)/sizeof(a1[0]);
int n = sizeof(a2)/sizeof(a2[0]);
printf("\n\n");
common(a1, a2, m, n);
getchar();
return 0;
}

The better answer is to use "counting sort" on these numbers. So make an int array of 8 in SIZE, and then a while loop to "walk" through both arrays, at the same time.

a2[] makes array[] look like this:

0 1 2 3 4 5 6 7
================
0 0 1 1 0 1 0 1

Because there was one 2, one 3, one 5, and one 7, in a2[].

Repeat the above with a1[]: (in the same loop), and get the results for both summed up:

0 1 2 3 4 5 6 7
================
0 1 2 2 1 2 1 1

Now the shared numbers are the one's with 2 in the array[] value. Only works when each array has unique numbers, otherwise you need to use two such arrays, and the elements with the same index number, that have 1 or more in them, are your common numbers.