#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/*
1a. Dane sa trzy tablice uporzadkowane niemalejaco:

1, 2, 2, 3, 5, 9, 9, 10, 11, 12, 12, 13, 14, 15, 15
0, 1, 3, 3, 5, 5, 6, 7, 8
0, 1, 2, 3, 7, 8, 9, 9, 9, 10

Znalezc i zwrocic pierwsza liczbe powtarzajaca sie we wszystkich trzech tablicach - tu 1

Inny wariant: wypisz wszystkie powtarzajace sie liczby - 1, 3

Przy braku takiej liczby zwroc -1
*/

// Porownywacz dla sortowania (rzutowanie na int)
int compare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

// prostsza wersja
int compare2(const void *a, const void *b) {
    int arg1 = *(const int *)a;
    int arg2 = *(const int *)b;

    if (arg1 < arg2) return -1;
    if (arg1 > arg2) return 1;
    return 0;
}

int* createAndFillArray(int n) {
    int *arr = (int *)malloc(n * sizeof(int));
    // Inicjalizacja generatora liczb losowych
    srand(time(NULL));
    // Wypelnienie tablicy losowymi liczbami
    for (int i = 0; i < n; i++) {
        arr[i] = rand() % (n + 1);  // Losowa liczba od 0 do n
    }
    // Sortowanie niemalejące tablicy (inclued from stdlib.h)
    qsort(arr, n, sizeof(int), compare2);
    return arr;
}
int findCommon(int sortedArray1[], int size1, int sortedArray2[], int size2, int sortedArray3[], int size3) {
    int i = 0, j = 0, k = 0;

    while (i < size1 && j < size2 && k < size3) {
        if (sortedArray1[i] == sortedArray2[j] && sortedArray2[j] == sortedArray3[k]) {
            return sortedArray1[i];
        } else if (sortedArray1[i] < sortedArray2[j]) {
            i++;
        } else if (sortedArray2[j] < sortedArray3[k]) {
            j++;
        } else {
            k++;
        }
    }

    return -1; // Jesli nie znaleziono wspolnego elementu
}

void findAllCommon(int sortedArray1[], int size1, int sortedArray2[], int size2, int sortedArray3[], int size3) {
    int i = 0, j = 0, k = 0, counter = -1;

    while (i < size1 && j < size2 && k < size3) {
        if (sortedArray1[i] == sortedArray2[j] && sortedArray2[j] == sortedArray3[k]) {
            printf("%d ", sortedArray1[i]);
            counter = 0;
            i++;
        } else if (sortedArray1[i] < sortedArray2[j]) {
            i++;
        } else if (sortedArray2[j] < sortedArray3[k]) {
            j++;
        } else {
            k++;
        }
    }
    if(counter==-1){
        printf("-1");
    }
}

void printArray(int array[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
}

int main() {

    // generujemy losowe tablice
    /*
    int n = 8; // Wielkosc tablicy
    int *sortedArray = createAndFillArray(n);
    printf("Tablica uporzadkowana niemalejaco:\n");
    for (int i = 0; i < n; i++) {
        printf("%d, ", sortedArray[i]);
    }
    printf("\n");
    free(sortedArray); // Zwolnienie pamieci
    */

    int sortedArray1[] = {0, 2, 2, 3, 5, 9, 9, 10, 11, 12, 12, 13, 14, 15, 15}; //15 elements
    int sortedArray2[] = {0, 3, 3, 5, 5, 6, 7, 8}; //8 elements
    int sortedArray3[] = {0, 1, 2, 3, 7, 8, 9, 9, 9, 10}; //10 elements

    int size1 = sizeof(sortedArray1) / sizeof(sortedArray1[0]);
    int size2 = sizeof(sortedArray2) / sizeof(sortedArray2[0]);
    int size3 = sizeof(sortedArray3) / sizeof(sortedArray3[0]);

    printArray(sortedArray1, size1);
    printArray(sortedArray2, size2);
    printArray(sortedArray3, size3);

    int common = findCommon(sortedArray1, size1, sortedArray2, size2, sortedArray3, size3);

    if (common != -1) {
        printf("\n\nPierwszy wspolny element we wszystkich trzech tablicach: %d\n", common);
    } else {
        printf("Brak wspolnego elementu we wszystkich trzech tablicach.\n");
    }

    printf("\nWszystkie wspolne elementy we wszystkich trzech tablicach: ");
    findAllCommon(sortedArray1, size1, sortedArray2, size2, sortedArray3, size3);
    printf("\n");

    return 0;
}