Hallo,
Gegeben ist ein Array[0..n-1], welches ganze Zahlen zw. 0 und n enthält. In diesem Array soll jetzt die fehlende Zahl x mit 0<= x <= n in O(n) ermittelt werden. Das schwierige ist jedoch das man nur auf das k-te Bit des i-ten Elements in kostanter Zeit zugreifen kann. Also ein Zugriff nur mittels A[k] zur Verfügung steht.
Mein Gedankengang war erstmal, das man überprüft ob eine gerade od. ungerade Zahl fehlt, welches ja anhand des ersten Bits leicht geprüft werden kann. Somit hätte man ja schon die hälfte der Möglichkeiten eliminiert. Jedoch hab ich noch keine Idee, wie ich jetzt weiter verfahren soll.
Hoffe mein Anliegen ist verständlich und ihr habt ein paar Ideen dazu