Storing numbers in array in C

Question

I have three one-dimensional arrays. The task is to store the numbers which exist in each of the three arrays in a forth array. Here is my solution which as you see isn't correct. I'm also interested in a faster algorithm if possible because it's O(N3) difficulty.

    #include <stdio.h>
main(){
int a[5]={1,3,6,7,8};
int b[5]={2,5,8,7,3};
int c[5]={4,7,1,3,6};
int i,j,k;
int n=0;
int d[5];
for(k=0; k<5; k++){
    for(j=0; j<5; j++){
        for(i=0; i<5; i++){
            if(a[i]==b[j] && b[j]==c[k])
                {d[n]=a[i];
                n++;}
            else
                d[n]=0;
    }}}
//Iterate over the new array
for(n=0;n<5;n++)
    printf("%d\n",d[n]);
return 0;
}

Petar Ivanov · Accepted Answer · 2011-06-18 11:25:13Z

7

One way to improve to O(n log n) is to sort all three arrays first. Then use three pointers one for each array. You always move the one that points to the lowest value and after every such move check whether the three values are the same.

To improve even further you can use hashtable. Iterate through the first array and put it's values in a hashtable as keys. Then iterate through the second array and every time when the value exists as a key in the first hashtable, put it in a second one. Finally iterate over the third array and if a value exists in the second hashtable as a key store it in the forth array. This is O(n) assuming the hashtable operations are O(1).

edited Jun 18, 2011 at 11:25

answered Jun 18, 2011 at 11:19

Petar Ivanov

93.4k11 gold badges84 silver badges95 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Ivan Danilov Over a year ago

You could get away just with two arrays sorted btw. If you have one of the arrays much shorter than the others - it'll speed up things significantly. See my answer for details.

Oliver Charlesworth · Accepted Answer · 2011-06-18 11:19:53Z

3

Your mistake is that you're using one of your three nested counters (which are being used to index the input arrays) as the index into the output array. You need to have a fourth index (let's call it n), which starts at zero, only increments every time a satisfactory value has been found.

answered Jun 18, 2011 at 11:19

Oliver Charlesworth

274k34 gold badges591 silver badges687 bronze badges

2 Comments

George Over a year ago

I changed the code as you suggested but there is some problem

Oliver Charlesworth Over a year ago

@George: You can edit your question to include your updated code! I can't read it when it's in a comment...

Ivan Danilov · Accepted Answer · 2011-06-18 11:21:08Z

3

Sort second and third arrays beforehand and use binary search on them to determine is some element is present. If element is present in all of your arrays - it will present in the first. So, go through first (unsorted) array and check if its element is in second and third.

If you take the shortest array as the first - it will make algorithm slightly faster too.

answered Jun 18, 2011 at 11:21

Ivan Danilov

14.9k6 gold badges52 silver badges66 bronze badges

Comments

aalku · Accepted Answer · 2011-06-18 15:11:27Z

1

You did't store them on d[] the right way.

Once found you can skip the rest of a[] and b[] for that element of c[].

#include <stdio.h>
main(){
int a[5]={1,3,6,7,8};
int b[5]={2,5,8,7,3};
int c[5]={4,7,1,3,6};
int i,j,k;
int n=0;
int found;
int d[5];
for(k=0; k<5; k++){
    found=0;
    for(j=0; j<5 && !found; j++){
        if (b[j]==c[k]) {
            for(i=0; i<5 && !found; i++){
                if(a[i]==b[j]) {
                    d[n++]=c[k];
                    found=1;
                }
            }
    }}}
//Iterate over the new array
for(i=0;i<5;i++)
    printf("%d\n",d[i]);
return 0;
}

edited Jun 18, 2011 at 15:11

answered Jun 18, 2011 at 11:49

aalku

2,8783 gold badges24 silver badges44 bronze badges

2 Comments

aalku Over a year ago

It's not a better algorithm but I think I fixed your code and it's slightly faster.

aalku Over a year ago

I added if (b[j]==c[k]) { as a optimization

Collectives™ on Stack Overflow

Storing numbers in array in C

4 Answers 4

1 Comment

2 Comments

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

2 Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related