一回で

前の問題と同様に進めます。各数値を3進法に変換します。b = b [0] + 3 * b [1] +3 ² * b [2] + ...各桁について、3を法とする値の合計を求めます（合計s [0]、s [1]、s [2]、...）。 さらに、数値自体を計算します。
シーケンス内の数値が3 * k + 1の場合、Xは1回満たされ、その値はs [0] + 3 * s [1] +3 ² * s [2] + ...数値が3 * k +の場合2、セットs [i]で単位を2に置き換える必要があり、その逆も同様です。x[i] =（3-s [i]）％3、X = x [0] + 3 * x [1] +3 ² * x [2] + ...

以前のアプローチはここでは機能しません：基数4の数値システムを使用してビット単位の量を見つけると、Xが1回または3回出会った場合、すべてがうまくいきます。 しかし、Xが2回出会った場合、次の桁が0であったか2であったかを調べることはできません。両方のケースでこの放電の合計siの値はゼロになります。 どうする
実際、私があなたを欺いた最後の時。 3進システムをいじる必要はまったくありませんでした。各2進数のビットの合計を計算するだけで十分であり、3で除算すると、対応するビットのXの数はゼロになりました。 そうでない場合は、1つ。
この問題では、まったく同じことを行いますが、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]という2つの行があります。
まず、各iについて、すべてのエントリの差b [i] -c [i]の合計s [i]を見つけた場合にどうなるかを見てみましょう。
名と姓を除くすべての名前が行bとcに同じ回数出現するため、合計すると名前が破棄され、名と姓のビットの差が合計に残ります。 したがって、s [i]の値は、-1、0、または1の値を取ることができます。
s [i] =-1の場合、名のb [i]の値は0、2番目の名前の値は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]は合計に2回（1回はb、2回目は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の1ビットカウンターと128の2ビットカウンターが必要です（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; } 

この手法を使用すると、2つまたは3つの要素を追加する（または2つを追加してから1つを削除する）ことによって取得されるセットの差を見つけることもできます。 差がより強い場合、ペアだけでなくビットのトリプルの接続詞の合計を保存する必要があります。 XORはすでに十分ではありません-少なくとも3ビットの交互合計を数える必要があります。

UPD：コメントでのこのタスクの議論で、 セプティムはよりシンプルなソリューションを提案しました。 名前を128ビット整数（xi、yi）と見なし、合計S1 =合計（xi-yi）、S2 =合計（xi ^ 2-yi ^ 2）（最初の合計は符号付き129ビット、2番目は-符号付き257ビット。オーバーフローを無視し、それぞれ2 ^ 129と2 ^ 257を法として動作します）。 それらの値がS1 = x1-xn、S2 = x1 ^ 2-xn ^ 2であることは明らかです。x1は名、xnは最後です。 これから、x1 =（S1 + S2 / S1）/ 2、xn = x1-S1を簡単に見つけることができます。

シーケンスから2つの異なる数字を消す場合、問題の条件は真のままであることに注意してください。 したがって、すべての要素が同じ数になるまで、異なる数のペアを消すことができます。 この番号はXです。
このメソッドを実装するために、シーケンスの一部の要素が格納されるセルと、カウンター-この要素のコピーをいくつ表示し、まだ削除していないかを開始しましょう。
次の要素を読むとき、次の3つのオプションがあります。
-カウンターはゼロです。 読み取り要素をセルに入れ、カウンターを1増やします。
-要素はセルの値と等しい。 カウンターを1増やします。
-アイテムがセルの値と等しくありません。 カウンターを1減らします。
シーケンス全体を調べた後、セルに目的の番号が表示されます。

残念ながら、数Xが1 / kの場合よりも多く発生する場合（kは既知）、この解決策を一般化することはできません。 また、カウンターでk-1セルを開始し、一度にk個の異なる要素を削除します。k-1の終わりにXの役割の候補を取得しますが、それを認識できません-カウンターの値が最大にならない場合でも。 ただし、2回目のパスを許可されている場合は、各候補者が順番に出会った回数を計算し、最も頻繁に保証されるものを提供できます。

元の問題には別の解決策があります。 各ビットごとに、それが0であった回数と1をカウントし、より頻繁に値を与えます。 おそらく、Xがケースの1/3を超える場合にそれをケースに一般化することが可能になるでしょう-ビットの各ペアの統計を計算しましょう...それが助けたらどうでしょうか？

解決策はほとんど同じです。 範囲0..M-1を2つ以上の部分に分割します。 各部分について、その中に含まれる数字の数を計算します。 最初の問題では、その長さよりも数が少ない最初のサブバンドを残します。2番目の問題では、長さよりも多くの数が落ちるサブバンドを残します。 このプロセスは、1つの数値の範囲が残るまで繰り返されます。 それが答えになります。