algorithm - n-1*n 配列が与えられた場合、欠落している数を見つけます

Question

ここで、各行には数値のビット表現が含まれています。これらの数値は 1..N から取得されます。正確に 1 つの数値が欠落しています。欠落した数値のビット表現を見つけます。
インタビュアーは私にこの質問をしました。
私は言った：「与えられた数の合計を見つけて、最初のn個の数の合計（（N *（N + 1））/ 2として知られている）から差し引くことができます」と
彼は言いました。基数 2. 基数
を変えずに解く方法を教えてください。

Answer 1

..範囲のXORすべての数値をまとめてから、配列の数値をまとめることができます。結果は欠番になります。0NXOR

説明: XOR数字自体を ing すると、常にゼロになります。上記XORのアルゴリズムは、欠けているものを除いて、各数値を正確に 2 回使用します。欠損値はXORゼロで 1 回だけ -ed されるため、結果は欠損値と等しくなります。

注: 足し算をするために基数を変換する必要があるというインタビュアーは間違っています: 2 進数の足し算は簡単で楽しいです - 実際、コンピューターは常にそれを行っています :-)

Answer 2

これらの数値を XOR し、1..n と XOR することができます。数値が 2 進数で格納されているという事実は、良いヒントです。

実際、演算子が可換である場合、順序は問題にならないため、逆演算子を持つ任意の可換演算子が機能するはずです。そのため、1..n の数値に適用できます。違いは最初のものではありません。配列にない数値で操作されました。次に、その逆数を使用してその数を見つけることができ、2 つの結果が得られます。SO +、-、*、/、XORおよびXOR要件を満たすその他の演算子はすべて、ここで機能する必要があります。