答えを探している問題は次のとおりです。
配列 A[1...n] には、1 つを除く 0 から n までのすべての整数が含まれます。補助配列 B[0...n] を使用して A に出現する数値を記録することにより、欠落している整数を O(n) 時間で簡単に特定できます。ただし、この問題では、A の整数全体にアクセスすることはできません。 1回の操作で。A の要素は 2 進数で表され、それらにアクセスするために使用できる操作は「A[i] の j 番目のビットをフェッチする」ことだけで、これには一定の時間がかかります。この演算だけを使用しても、不足している整数を O(n) 時間で決定できることを示してください。
私はこのアプローチを念頭に置いています。上記のフェッチ制限がなければ、すべての数値を取得してそれらの XOR を一緒に実行したでしょう。次に、結果を 1..n のすべての数値で XOR します。そして、この結果が私の答えになります。この問題では、同様に、配列内のすべての要素について、log(n+1) ビットの距離にある異なる数のビットを繰り返し XOR し、要素 1...n と XOR することができますが、複雑さは次のようになります。私の意見では O(nlogn) です。
O(n) の複雑さを達成する方法は? ありがとう