Find common element in two from three arrays

Question

I need to find elements of array which are hold in two of three given arrays. It seems easy, but it's quite dificult and i have been strugling with this for few days. I hope you can help me..

For input:

1 2 3 5

1 2 4 6 7

1 3 4 8 9 10

Output should be 3 (because 3,4,2 are common for two arrays)

for input

1 2 3 4

2 3 4

3 4 1

Output should be: 2 (because 1 is common for two arrays)

Here is my code:

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

int main()
{
    int duzina_prvog_niza = 0, duzina_drugog_niza = 0, duzina_treceg_niza = 0; //deklaracija duzina nizova
    printf("Unesite broj clanova prvog niza:\n");                              // unosimo duzine nizova i elemente nizova
    do
    {
        scanf("%d", &duzina_prvog_niza);
    } while (0 > duzina_prvog_niza || duzina_prvog_niza > 50); // mozda ne bi trebalo stavljati gornju granicu za duzinu niza
    int niz1[duzina_prvog_niza];                               //zavisi kako vam sistem provjere radi, mislim da nece praviti problem
    // alociramo niz odgovarajuce duzine, iterativno popunimo niz uz odgovarajucu provjeru
    for (int i = 0; duzina_prvog_niza > i; i++)
    {
        do
        {
            scanf("%d", &niz1[i]);
        } while (0 > niz1[i] || niz1[i] > 10); // citaj elemente sve dok ne ucitas cifre iz odgovarajuceg opsega
    }
    for (int i = 0; duzina_prvog_niza > i; i++)
        printf(" %d  ", niz1[i]);
    printf("\n");
    // ** drugi niz **       -- bilo bi zgodno ovo sve strpati u jednu fju, meni je ovako bilo lakse..  c/p
    printf("Unesite broj clanova drugog niza:\n");
    do
    {
        scanf("%d", &duzina_drugog_niza);
    } while (0 > duzina_drugog_niza || duzina_drugog_niza > 50);
    int niz2[duzina_drugog_niza];
    // alociramo niz odgovarajuce duzine, iterativno popunimo niz uz odgovarajucu provjeru
    for (int i = 0; duzina_drugog_niza > i; i++)
    {
        do
        {
            scanf("%d", &niz2[i]);
        } while (0 > niz2[i] || niz2[i] > 10); // citaj elemente sve dok ne ucitas cifre iz odgovarajuceg opsega
    }
    for (int i = 0; duzina_drugog_niza > i; i++)
        printf(" %d  ", niz2[i]);
    printf("\n");

    // ** treci niz **
    printf("Unesite broj clanova treceg niza:\n");
    do
    {
        scanf("%d", &duzina_treceg_niza);
    } while (0 > duzina_treceg_niza || duzina_treceg_niza > 50);
    int niz3[duzina_treceg_niza];
    // alociramo niz odgovarajuce duzine, iterativno popunimo niz uz odgovarajucu provjeru
    for (int i = 0; duzina_treceg_niza > i; i++)
    {
        do
        {
            scanf("%d", &niz3[i]);
        } while (0 > niz3[i] || niz3[i] > 10); // citaj elemente sve dok ne ucitas cifre iz odgovarajuceg opsega
    }
    for (int i = 0; duzina_treceg_niza > i; i++)
        printf(" %d ", niz3[i]);
    printf("\n");

    //pocetna vrijednost brojaca mora biti nula!
    int brojac = 0;
    int pomocni_brojac = 0;
    // (S_1 intersect S_2) union (S_2 intersect S_3) union (S_3 intersect S_1)  -- matematicko rjesenje problema

    int x;
    int pomocni_niz[duzina_prvog_niza + duzina_drugog_niza + duzina_treceg_niza];
    for (int i = 0; duzina_prvog_niza + duzina_drugog_niza + duzina_treceg_niza > i; i++)
        pomocni_niz[i] = 0;

    int max;
    if(duzina_prvog_niza>=duzina_drugog_niza && duzina_prvog_niza>=duzina_treceg_niza) max=duzina_prvog_niza; 
    if(duzina_drugog_niza>=duzina_prvog_niza && duzina_drugog_niza>=duzina_treceg_niza) max=duzina_drugog_niza; 
    if(duzina_treceg_niza>=duzina_drugog_niza && duzina_treceg_niza>=duzina_prvog_niza) max=duzina_treceg_niza; 

    //prolazimo kroz sve elemente u sva tri niza i poredimo sve elemente sa svim elementima
    for (int i = 0; duzina_prvog_niza > i; i++)
    {
        for (int j = 0; duzina_drugog_niza > j; j++)
        {
            for (int k = 0; duzina_treceg_niza > k; k++)
            { // ako je element iz prvog niza jednak elementu iz drugog niza, ili je element
                if (((niz1[i] == niz2[j]) && (niz2[j] == niz3[k]) && (niz1[i] == niz3[k])))
                    1;
                else if ((niz1[i] != niz2[j]) && (niz2[j] == niz3[k]) && (niz1[i] != niz3[k]))
                    pomocni_niz[pomocni_brojac++] = niz2[j];
                else if ((niz1[i] == niz2[j]) && (niz2[j] != niz3[k]) && (niz1[i] != niz3[k]))
                    pomocni_niz[pomocni_brojac++] = niz1[i];
                else if ((niz1[i] != niz2[j]) && (niz2[j] != niz3[k]) && (niz1[i] == niz3[k]))
                    pomocni_niz[pomocni_brojac++] = niz2[j];
            }
        }
    }

int y = 0;
    for (int g = 0; pomocni_brojac > g; g++)
    {
        for (int l = 0; pomocni_brojac > l; l++)
        {
            if (pomocni_niz[g] == pomocni_niz[l])
                y++;
        }
        if (y == 0)
            brojac++;
        y = 0;
    }

    for (int i = 0; brojac > i; i++)
        printf("%d ", pomocni_niz[i]);
    printf("U dva od tri niza se nalazi %d clanova.", brojac);
 
    return 0;
}

Thanks!

Answer 1

There exists a pretty fast solution to your problem. You will need three more arrays each having a size of 100. Each array will record the frequency of any particular input array. The size of each frequency array is 100 since any input array will only consist of numbers in the range 0-99.

For example:

Input arrays:

A: 1 2 3 5
B: 1 2 4 6 7
C: 1 3 4 8 9 10

Frequency arrays:

   0 1 2 3 4 5 6 7 8 9 10

A: 0 1 1 1 0 1 0 0 0 0 0
B: 0 1 1 0 1 0 1 1 0 0 0
C: 0 1 0 1 1 0 0 0 1 1 1

In the frequency arrays section:

The top row denotes number which may be present in any input array and the rows below contains their frequency in each input array..

---

Algorithm

1 : let frequencyA[100]
2 : let frequencyB[100]
3 : let frequencyC[100]
4 :
5 : for i = 0 to A.length-1
6 :     if (frequencyA[A[i]] == 0) frequencyA[A[i]]++
7 : for i = 0 to B.length-1
8 :     if (frequencyB[B[i]] == 0) frequencyB[B[i]]++
9 : for i = 0 to C.length-1
10:     if (frequencyC[C[i]] == 0) frequencyC[C[i]]++
11:
12: for i = 0 to 99
13:     if (frequencyA[i]+frequencyB[i]+frequencyC[i] == 2) Print i

The algorithm is pretty straight forward. The only that lines that deserve some explanation are mentioned below.

Line 5-10:

For each input array, we loop though each of its element and record their frequency. We record the frequency of any particular element only once, that is, if any element repeats in a single array, we will record its frequency only once. This is made sure by the if condition which checks if we have recorded the frequency of any element before or not.

Line 12-13:

We start a loop from 0 to 99 since they are the possible values of the array. In the loop, we check if sum of the frequency in the all the three frequency arrays of any element is 2 or not. If its 2, then that element is present in present exactly twice else not.

---

Time Complexity

The algorithm has a time complexity of O(A.length + B.length + C.length). It is a linear time complexity which is quite fast.

---

I can not provide you with any code as I do not code in C a lot. I hope I have helped you. If you face any trouble in understanding my answer, please do comment. I will be happy to update my answer.

Answer 2

For starters always use English words for identifiers. In this case your code will be readable for a larger auditorium. Otherwise it is difficult to read it.

This statement in your program

if (((niz1[i] == niz2[j]) && (niz2[j] == niz3[k]) && (niz1[i] == niz3[k])))
                    1;

does not make a sense.

If you need to output common elements that are present exactly in two of three arrays then there is no great sense to create a forth array with the size equal to the sum of sizes of the three arrays.

If the arrays can be unsorted and you may not sort the arrays then a straightforward approach can look the following way as it is shown in the demonstrative program below.

#include <stdio.h>

void f( const int a1[], size_t n1, const int a2[], size_t n2, const int a3[], size_t n3 )
{
    size_t total = 0;
    
    for ( size_t i1 = 0; i1 < n1; i1++ )
    {
        size_t count = 1;
        
        size_t i2 = 0;
        while ( i2 < n2 && a2[i2] != a1[i1] ) i2++;
        
        count += i2 != n2;
        
        size_t i3 = 0;
        while ( i3 < n3 && a3[i3] != a1[i1] ) i3++;
        
        count += i3 != n3; 
        
        if ( count == 2 )
        {
            ++total;
            printf( "%d ", a1[i1] );
        }
    }

    for ( size_t i2 = 0; i2 < n2; i2++ )
    {
        size_t i1 = 0;
        while ( i1 < n1 && a1[i1] != a2[i2] ) i1++;
        
        if ( i1 == n1 )
        {
            size_t i3 = 0;
            while ( i3 < n3 && a3[i3] != a2[i2] ) i3++;
        
            if ( i3 != n3 )
            {
                ++total;
                printf( "%d ", a2[i2] );
            }               
        }
    }
    
    if ( total != 0 ) putchar( '\n' );
    
    printf( "%zu\n", total );
}

int main(void) 
{
    int a[] = { 1, 2, 3, 5 };
    int b[] = { 1, 2, 4, 6, 7 };
    int c[] = { 1, 3, 4, 8, 9, 10 };
    size_t n1 = sizeof( a ) / sizeof( *a );
    size_t n2 = sizeof( b ) / sizeof( *b );
    size_t n3 = sizeof( c ) / sizeof( *c );

    f( a, n1, b, n2, c, n3 );
    
    return 0;
}

The program output is

2 3 4 
3