За один проход

Задача 8 может решаться в один проход "подсчетом", отличающимся тем что считать нужно только однобитовый флаг присутствия (значит рабочая память будет M/8 байт) и тем, что при первой же необходимости прирастить счет значения которое уже равно 1 мы заканчиваем)
Если из условия "Задача 8. В последовательности записано M+1 целое неотрицательное число" предполагать что сама последовательность влезает в память компьютера. (Хотя это может быть не так)

(Пишу потому что) Хотя иначе мы приходим все же к вашей же сложности, но с более практическим пониманием идеи диапазонов. Мы выделяем столько счетчиков "парности" сколько можем по памяти, а после считаем присутствие для значений, N старших бит которого указывают соответствующий групповой счетчик. (Эта классика и вызывает у меня стойкую ассоциацию с сортировкой подсчетом)

Оценка по памяти: 1Гб сможет адресовать 8_388_608 диапазонов по 23 старшим битам. Последующими проходами мы просто игнорируем все не интересующее за пределами выбранного диапазона (идентифицированного по старшим битам) и точно так же индексируем значения внутри него по следующим битам, повторяя пока биты не закончатся. Т.о. например за три прохода даже с 512Мб памяти мы уже сможем решать это для 64битных значений M.

Счетчиками парности я их назвал наводя на идею о том, что если завести не однобитовые а больше флаги, то можно искать таким образом и наибольшие/наименьшие значения встречающиеся более/менее чем N раз. Например с 4Гб памяти за 3 прохода можно найти наименьшее/большее 64битное число встречающееся более 2 или 3 раз. (что на больших разреженных числах выглядит довольно полезным инструментом выявления каких-то корреляций. Практическое приложение - анализ коллизий хэш функций/ или случайных генераторов на домашнем компе)

log=async(...arg)=>new Promise(r=>{  //async log
    console.log(...arg); setTimeout(r);
})
async function someCollisionOfUi32(iterable){
    const map=new Uint32Array(65536); //256K
    // поиск группы с кол-вом членов >65535 (минимум 1 повторился):
    let i=0, collision= Math.floor(Math.random()*0x100000000);
    console.log('predefined collision was:', collision);
    for(x of iterable(collision, 123)){
        if(!(++i&0x3FFFFFF))await log((i/0x100000000).toFixed(2));
        if(++map[x>>>=16] > 65536){
            map.fill(0);
            // поиск числа из группы повторившегося более раза
            for(y of iterable(collision, 123)){
                if(!(++i&0x3FFFFFF))await log((i/0x100000000).toFixed(2));
                if((y>>>16)==x&&map[y&65535]++)return y; //гарантированно случиться
            }
            break;
        };
    }
    return -1; //дубли отсутствуют
}

function*TestSeq(mix, seed=Math.floor(Math.random()*0x100000000)){    
    let x=new Uint32Array(1);
    x[0]=seed;
    for(let n=0;n<0x100000000;n++){
        x[0]=x[0]*69069 +1; // Ui32 modulo by overflow
        yield x[0];
    }
    yield mix; yield mix;
    return;
}
// console.log([...TestSeq(4)])

console.time("collise");
console.log('someCollisionOfUi32:',await someCollisionOfUi32(TestSeq));
console.timeEnd("collise"); //~219s

Попробовал решение 8й задачи на всех ui32 числах. С тестом как водиться провозился дольше чем с алгоритмом. В итоге:
- тест на JS и работает из консоли браузера
- лог асинхронный (что позволяет вкладке не виснуть намертво до конца выполнения) выводит процент готовности прохода в консоль (всего их два)
- потребление памяти 256Кб
- скорость обхода 2**k+2 чисел ~219s (3 с половиной минуты на ryzen 9)
- тестируется LCG PRNG последовательность всех ui32 чисел + в конец ее добавляется дважды случайно взятое число (оно и будет давать коллизию)

Дополнения:
- в принципе 2**32 чисел это всего то 2**29 = 536 870 912 байт индекса, что можно побитово замапить флагами четности и решить за один проход вдвое быстрее, но потратив 512Мбайт вместо 256Кбайт. Можно оценить разницу по памяти. Впрочем работая с ui64 надо именно так поступать, потому что битность кратно уменьшает кол-во проходов. Я потестил ui32 версию потому что хотелось строгий тест провести с наличием всех чисел. А для ui64 их в 2*32 раз больше... В принципе адаптировать из этого теперь элементарно. Но на полной последовательности просто забейте это дома считать...
- на самом деле для хранения переполнения 16битным счетчикам не хватало бы 1го значения. Пробовал версию которая бьет диапазоны по 65535 чисел - тогда памяти требуется даже 128K + 8б, но из-за делений индексов и взятия остатков по модулю не степени 2ки - где-то вдвое падает производительность. Можно отдельные флаги переполнения ввести для групп потратив +8К и по скорости будет почти также. Но будет более запутанный код.
- забавно сразу же прикладной фактор показал себя... пока тестил пришлось взять линейный конгруэнтный генератор, взял первый попавшийся из вики, и бах алг что то выбрасывает раньше, гляжу опять в вики в генераторе написано, что не все биты в нем используются (т.е. нет полной конгруэнтности, значит есть дубли) - и алг уже это показывал сразу. Причем даже с случайным сидом в основном отбрасывал на нескольких конкретных числах. Если бы нужно было проанализировать этот генератор, это была бы ценная информация для оценки куда копать