Как найти в последовательности чисел наименьшее число

Предыдущий подход здесь уже не сработает: если мы возьмём систему счисления с основанием 4, и найдём поразрядные суммы, то для случаев, когда X встретился один или три раза, всё будет хорошо. Но если X встретился дважды, мы уже не сможем узнать, была ли очередная цифра равна 0 или 2 — значение суммы si для этого разряда в обоих случаях будет равно нулю. Что делать?
На самом деле, в прошлый раз я вас обманул. Совершенно незачем возиться с троичной системой — достаточно было посчитать сумму битов в каждом двоичном разряде, и если она делилась на 3, то в числе X соответствующий бит равнялся нулю. Если нет — то единице.
В этой задаче делаем точно так же, но проверяем делимость на 4. Например, эти задачи можно решить так:

        static int FindNotThree(IEnumerable<int> seq) {
            int a=0,b=0;
            foreach(int c in seq) {
                a^=~b&c;
                b^=~a&c;
            }
            return a|b;
        }
        static int FindNotFour(IEnumerable<int> seq) {
            int a=0,b=0;
            foreach(int c in seq) {
                a^=b&c;
                b^=c;
            }
            return a|b;
        }

Будем рассматривать каждое имя, как битовую строчку из 128 элементов. В каждой записи у нас две таких строчки — b[i] и c[i].
Cначала посмотрим, что получится, если для каждого i мы найдём сумму s[i] разностей b[i]-c[i] для всех записей.
Поскольку все имена, кроме первого и последнего, встречаются в строчках b и c однаковое число раз, то при суммировании они взаимоуничтожатся, и в сумме останется поразрядная разность первого и последнего имени. Значение s[i], таким образом, может принимать значения -1, 0 или 1.
Если s[i]=-1, то значение b[i] для первого имени равно 0, а для второго 1. Если s[i]=1, то значения будут равны 1 и 0 соответственно. Но если s[i]=0, то мы можем сказать только, что значения этого бита в первом и последнем имени одинаковы. Как бы нам их найти?
Предположим, что мы знаем, что для какого-то k у нас s[k] ненулевое. Что будет, если мы найдём XOR значений (b[i]&b[k])^(c[i]&c[k])?
Для всех имён n, кроме первого и последнего, выражение n[i]&n[k] войдёт в сумму дважды (один раз как b, второй раз, как c) и даст нулевой вклад. Если f — первое имя, а p — последнее, то в сумме останется (f[i]&f[k])^(p[i]&p[k]). Нас интересуют только те биты, для которых f[i]=p[i] (значения остальных мы уже нашли). Поэтому, (f[i]&f[k])^(p[i]&p[k])=f[i]&(f[k]^p[k]), а поскольку s[k]!=0, то f[k]^p[k]=1, и итоговая сумма равна f[i].
К сожалению, сказать заранее, в каком бите будут различаться имена, мы не можем. Поэтому, на всякий случай, будем считать суммы
(b[i]&b[k])^(c[i]&c[k]) для всех пар i,k. Всего нам понадобится 128*127/2=8128 однобитных счётчиков и 128 двухбитных (для подсчёта s[i]).
Например, можно написать обработку так (мы предполагаем, что оба имени в записи передаются в одном байтовом массиве, записанные подряд):

        static byte[] FindDiffNames(IEnumerable<byte[]> seq) {
            const int LName=16;
            byte[,] pairs=new byte[LName*8,LName];
            byte[] res=new byte[2*LName];

            foreach(byte[] name in seq) {
                for(int i=0;i<LName;i++) {
                    res[i+LName]^=(byte)(name[i]&res[i]);
                    res[i]^=(byte)(name[i]^name[i+LName]);
                    res[i+LName]^=(byte)(name[i+LName]&res[i]);
                    for(int k=0;k<LName*8;k++) {
                        byte mask=(byte)(1<<(k&7));
                        if((name[k>>3]&mask)!=0) pairs[k,i]^=name[i];
                        if((name[LName+(k>>3)]&mask)!=0) pairs[k,i]^=name[i+LName];
                    }
                }
            }
            for(int i=0;i<LName;i++) {
                int b0=res[i],b1=res[i+LName],s=0;
                for(int j=0;j<LName*8;j++) s|=pairs[j,i];
                s&=~b0;
                res[i]=(byte)((b0&~b1)|s); res[i+LName]=(byte)((b0&b1)|s);
            }
            return res;
        }

С помощью этого приёма можно, также, найти разность множеств, одно из которых получается из другого добавлением двух или даже трёх элементов (или добавлением двух и удалением одного). Если различия более сильные, приходится хранить суммы конъюнкций не только пар, но и троек битов. И XOR там уже недостаточно — приходится считать хотя бы трёхбитные знакопеременные суммы.

UPD: В обсуждении этой задачи в комментариях SeptiM предложил более простое решение. Рассматриваем имена как 128-битные целые числа (xi,yi), и считаем суммы S1=sum(xi-yi), S2=sum(xi^2-yi^2) (первая сумма должна быть знаковой 129-битной, вторая — знаковой 257-битной. Переполнения игнорируем, работаем по модулю 2^129 и 2^257 соответственно). Понятно, что их значения равны S1=x1-xn, S2=x1^2-xn^2, где x1 — первое имя, xn — последнее. Отсюда легко находим x1=(S1+S2/S1)/2, xn=x1-S1.

Заметим, что если мы вычеркнем из последовательности два различных числа, то условие задачи останется верным. Поэтому мы можем вычёркивать пары различных чисел до тех пор, пока все элементы не станут равными одному и тому же числу. Это число и будет X.
Чтобы реализовать этот метод, заведём ячейку, в которой будет храниться какой-то элемент последовательности, и счётчик — сколько копий этого элемента у нас просмотрено и пока не вычеркнуто.
Когда мы читаем очередной элемент, у нас есть три варианта:
— Счётчик равен нулю. Кладём прочитанный элемент в ячейку, увеличиваем счётчик на 1.
— Элемент равен значению ячейки. Увеличиваем счётчик на 1.
— Элемент не равен значению ячейки. Уменьшаем счётчик на 1.
После того, как мы просмотрим всю последовательность, в ячейке окажется искомое число.

К сожалению, обобщить это решение на случай, когда число X встречается больше, чем в 1/k случаев (k известно), не удаётся. Мы можем так же завести k-1 ячейку со счётчиком, удалять за один раз по k различных элементов, получим в конце k-1 кандидата на роль X, но опознать его нам не удастся — даже значение счётчика у него будет не самым большим. Зато если нам разрешат сделать второй проход, мы можем посчитать, сколько раз каждый из кандидатов встретился в последовательности, и выдать гарантированно самого частого.

У исходной задачи есть ещё одно решение. Для каждого бита считаем, сколько раз он равнялся 0, а сколько — 1, и выдаём более частое значение. Возможно, его удастся обобщить на случай, когда X встречается больше, чем в 1/3 случаев — посчитаем статистику для каждой пары битов… вдруг поможет?