Поиск повторяющихся целых чисел со знаком с O (n) во времени и O (1) в пространстве

(Это обобщение: Поиск дубликатов в O (n) время и O (1) пространство )

Проблема: напишите функцию C ++ или C со временными и пространственными сложностями O (n) и O (1) соответственно, которая находит повторяющееся целое в заданном массиве, не изменяя его.

Пример: для заданных {1, 0, -2, 4, 4, 1, 3, 1, -2} функция должна вывести 1, -2 и 4 один раз (в любом порядке).

РЕДАКТИРОВАТЬ: Следующее решение требует двойного бита (для представления 0, 1 и 2) для каждого целого числа в диапазоне от минимума до максимума массива. Количество необходимых байтов (независимо от размера массива) никогда не превышает (INT_MAX – INT_MIN)/4 + 1.

#include 

void set_min_max(int a[], long long unsigned size,\
                 int* min_addr, int* max_addr)
{
    long long unsigned i;

    if(!size) return;
    *min_addr = *max_addr = a[0];
    for(i = 1; i < size; ++i)
    {
        if(a[i] < *min_addr) *min_addr = a[i];
        if(a[i] > *max_addr) *max_addr = a[i];
    }
}

void print_repeats(int a[], long long unsigned size)
{
    long long unsigned i;
    int min, max = min;
    long long diff, q, r;
    char* duos;

    set_min_max(a, size, &min, &max);
    diff = (long long)max - (long long)min;
    duos = calloc(diff / 4 + 1, 1);
    for(i = 0; i < size; ++i)
    {
        diff = (long long)a[i] - (long long)min; /* index of duo-bit
                                                    corresponding to a[i]
                                                    in sequence of duo-bits */
        q = diff / 4; /* index of byte containing duo-bit in "duos" */
        r = diff % 4; /* offset of duo-bit */
        switch( (duos[q] >> (6 - 2*r )) & 3 )
        {
            case 0: duos[q] += (1 << (6 - 2*r));
                    break;
            case 1: duos[q] += (1 << (6 - 2*r));
                    printf("%d ", a[i]);
        }
    }
    putchar('\n');
    free(duos);
}

void main()
{
    int a[] = {1, 0, -2, 4, 4, 1, 3, 1, -2};
    print_repeats(a, sizeof(a)/sizeof(int));
}