Finden der fehlenden Zahl in einem Array

[smoon]

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

[Jan Jansen]

Such einen (Nicht-)Gruppenwechsel Gerade/Ungerade

[smoon]

Hatte vergessen dazu zu schreiben, dass es sich um ein unsortietes Array handelt.

[Klotzkopp]

Die Gesamtzahl der gesetzten Bits an Stelle k für alle Zahlen von 0 bis n steht fest. Wenn du dein Array nachzählst, und deine Summe für ein bestimmtes Bit um 1 zu klein ist, ist dieses Bit bei der fehlenden Zahl gesetzt.

[TDM]

Such einen (Nicht-)Gruppenwechsel Gerade/Ungerade

1, 2, 3, 4, 7, 8, 9

Oder fehlt immer nur eine Zahl?

[smoon]

Die Gesamtzahl der gesetzten Bits an Stelle k für alle Zahlen von 0 bis n steht fest. Wenn du dein Array nachzählst, und deine Summe für ein bestimmtes Bit um 1 zu klein ist, ist dieses Bit bei der fehlenden Zahl gesetzt.

Das würde doch bedeuten das ich für jedes Element einmal alle Bits durchgehen muss. Dies würde jedoch einen Aufwand von O(n²) haben, oder hab ich jetzt was falsch verstanden?

[smoon]

1, 2, 3, 4, 7, 8, 9

Oder fehlt immer nur eine Zahl?

Ja es fehlt immer nur eine Zahl.

[Klotzkopp]

Das würde doch bedeuten das ich für jedes Element einmal alle Bits durchgehen muss. Dies würde jedoch einen Aufwand von O(n²) haben, oder hab ich jetzt was falsch verstanden?

Der Aufwand wäre O(n log n), aber natürlich hast du damit im Prinzip Recht. Bearbeitet 15. Mai 2008 von Klotzkopp

[smoon]

Gesucht ist jedoch leider ein Algorithmus, welcher dies in O(n) erledigt

[Klotzkopp]

Gesucht ist jedoch leider ein Algorithmus, welcher dies in O(n) erledigt

Da sehe ich schwarz. Wenn man ganze Zahlen auf einmal verknüpfen könnte, ginge das in O(n), aber man braucht ja schon O(n log n), um überhaupt auf alle Bits zuzugreifen.

Oder ist das ein Array eines konkreten integralen Datentyps, d.h. die Anzahl der Bits ist irgendwie beschränkt?

[smoon]

Ja ich würde annehmen, dass die Bits in Abhängigkeit von n beschränkt sind. Denn ln(n)/ln(2) aufgerundet ergibt ja die Anzahl der Bits die benötigt werden um n als Dualzahl darzustellen.

[Klotzkopp]

Ja ich würde annehmen, dass die Bits in Abhängigkeit von n beschränkt sind. Denn ln(n)/ln(2) aufgerundet ergibt ja die Anzahl der Bits die benötigt werden um n als Dualzahl darzustellen.

Das ist klar. Ich meinte, ob die Anzahl der Bits absolut beschränkt ist, z.B. weil es sich um ein Array eines 32-Bit-Datentyps handelt.

Aber das wäre wohl Unsinn, denn dann wäre sowieso alles in O(1) machbar, denn mit der Anzahl der Bits wäre auch n selbst beschränkt.

[flashpixx]

Hallo,

wenn ich das richtig verstehe - bitte korrigiert mich - hab ich ein Element mit n-1 Zahlen aus N.

Ich kann doch einfach iterativ durch gehen und summieren, einmal über das Arrayelement und einmal über den Zähler. Der Zähler beginnt bei 0 und endet bei n-1, d.h. die beiden Summen müssten identisch sein, da sie beide bei 0 beginnen.

Da es iterativ ist ergibt sich formal doch O(c*n) = O(n)

Ich hoffe ich hab das jetzt auf die Schnelle korrekt verstanden

Phil

[smoon]

Um die Werte zu summieren, müsstest man einmal jedes Element durchgehen => O(n) und die einzelnen Bits jedes Elements 0 => O(log n). Das ergibt dann eine Komplexität von O(n log n), wie Klotzkopp schon erwähnt hat.

[Klotzkopp]

Da es iterativ ist ergibt sich formal doch O(c*n) = O(n)

Wenn du auf die ganzen Zahlen zugreifen könntest, ja. Du kannst aber nur auf einzelne Bits zugreifen. Damit ist die Addition zweier Zahlen nicht mehr in konstanter Zeit möglich, sondern hängt linear von der Anzahl der Bits ab. Die wiederum hängt vom Logarithmus der Anzahl der Zahlen ab.

[flashpixx]

Hallo,

ich hab das mit den "Bits" überlesen. Sorry

Phil

[Jan Jansen]

Wie wäre folgende Lösung:

1. Durchsuche das Array nach gerade und ungerade (letztes Bit) und schreibe die Positionen je nach Gerade/Ungerade in ein eigenes Array

2. Anhand der Anzahl Gerade/Ungerade kann man bestimmen ob die gesuchte Zahl Gerade/Ungerade ist

-> 1. Stelle gefunden, n Lesevorgänge

3. Suche in der eingeschränkten Ausgangsmenge (Zugriff über das Gerade oder Ungerade-Array) jetzt nach der 2. Stelle und speicher die Positionen wieder in 2 unterschiedlichen Array

Je nach Anzahl kann man wieder bestimmen ob das 2. Bit Gerade/Ungerade ist

-> 2. Stelle gefunden, aber nur noch 1/2*n Lesevorgänge

So geht man alle Stellen durch und verkleinert die Restmenge der Zahlen die durchsucht werden muss immer um 1/2

n + 1/2*n + 1/4*n ... = n*(1+1/2+1/4 ...)

das wäre ein Aufwand der Ordnung n

[smoon]

Dies scheitert schon am dynamischen erstellen der Arrays nach jedem Durchgang.

[Jan Jansen]

Naja, es geht ja weniger um die Technik, als um einen Algorithmus um dein Problem zu lösen.

Ob du jetzt die Werte in einem Array merkst, einem File, einer verketten Liste sollte eigentlich egal sein

Bearbeitet 15. Mai 2008 von Jan Jansen

[smoon]

Dennoch bin ich der Meinung das dieser Algorithmus nicht die Komplexität O(n) hat, denn du wiederholst ja die Schritte (log n)-Mal. Also wäre es doch wieder O(n log n). Bitte korrigiert mich falls ich falsch liege!

[Klotzkopp]

Ob du jetzt die Werte in einem Array merkst, einem File, einer verketten Liste sollte eigentlich egal sein

Das Problem bleibt aber, dass man nicht auf einen ganzen Wert zugreifen kann, nur auf einzelne Bits. Man kann also die Werte auch nicht in konstanter Zeit umkopieren.

[smoon]

Ich glaub er meinte nicht das man die Bits umkopiert, sondern sich lediglich jeweils die Positionen der gerade/ungerade werte "merkt".

[flashpixx]

Hallo nochmal,

was soll eigentlich genau gemacht werden?

Ich habe das Ursprungsposting noch mal gelesen. Die Beschränkung ist klar, ich kann immer nur ein Bit in const. Zeit lesen.

Ist jetzt die Fragestellung:

• Gib es einen Algorithmus mit O(c*n), mit dem man prüfen kann, ob alle Zahlen von 0 bis n-1 vorhanden sind?
  
• Muss man diese Aufgabenstellung implementieren z.B. Pseudocode?
  
• Ist zu zeigen, dass es diesen Algorithmus gibt, d.h. ein allgemein gültigen Beweis zu führen bzw. ihn zu widerlegen?
  

Phil

[smoon]

Ist jetzt die Fragestellung:

• Gib es einen Algorithmus mit O(c*n), mit dem man prüfen kann, ob alle Zahlen von 0 bis n-1 vorhanden sind?
  
• Muss man diese Aufgabenstellung implementieren z.B. Pseudocode?
  
• Ist zu zeigen, dass es diesen Algorithmus gibt, d.h. ein allgemein gültigen Beweis zu führen bzw. ihn zu widerlegen?
  

• Nein es soll die Fehlende Zahl im Array ermittelt werden, in O(n).
  
• Ja der Algorithmus soll in Pseudocode implementiert werden.
  
• Nein es ist nichts zu beweisen.
  

[Jan Jansen]

Dennoch bin ich der Meinung das dieser Algorithmus nicht die Komplexität O(n) hat, denn du wiederholst ja die Schritte (log n)-Mal. Also wäre es doch wieder O(n log n). Bitte korrigiert mich falls ich falsch liege!

Der Aufwand für jeden Schritt wird aber erheblich kleiner

Die Anzahl der Summanden in der Klammer ist abhängig von n bzw. von der Anzahl der Bits

n + 1/2*n + 1/4*n ... = n*(1+1/2+1/4 +1/8+1/16 ...)

für mich läuft dieser Wert (bei sehr großen n) auf eine Konstante heraus, laut Wikipedia/Englisch konvergiert er auf 1+1=2