# Knobelaufgabe Java



## gast1234 (5. Jun 2021)

Hey Leute, sitze schon seit geraumer Zeit an dieser Aufgabe, aber komme einfach überhaupt nicht weiter...hätte jemand vielleicht Hilfestellungen, Anregungen, Lösungen o.ä.?  Würde mich über jede Art der Hilfe freuen. 

Zur Aufgabe: 
In einem Feld mit n > 0 Eintragen sind n paarweise verschiedene ganzzahlige Werte aus dem Bereich [0... n] in unsortierter Folge gespeichert. Es ist also genau ein Wert aus dem Bereich [0... n] nicht(!) in dem Feld vorhanden; dieser Wert soll bestimmt werden. Im folgenden sollen zwei Algorithmen mit linearer Laufzeit angegeben werden, die das obige Problem lösen. Zugelassen ist Java-Code oder auch Pseudocode-Darstellungen.

Danke schonmal im voraus!


----------



## LimDul (5. Jun 2021)

Gaussche Summenformel - die Abweichung der Summe aller Zahlen im Feld gegenüber der erwarteten Summe ist die fehlende Zahl


----------



## CyborgIstDoof (5. Jun 2021)

LimDul hat gesagt.:


> Gaussche Summenformel - die Abweichung der Summe aller Zahlen im Feld gegenüber der erwarteten Summe


hätte ich jetzt auch gesagt, aber es ginge auch mit einem Bitset der Länge n.


```
public static void main(String[] args) {
        int[] a = { 0, 5, 4, 2, 1 };
        BitSet set = new BitSet(a.length);
        for (int i : a) {
            set.set(i);
        }
        long n2 = ~(-1L << (a.length + 1));
        System.out.println(Math.log(~set.toLongArray()[0] & n2) / Math.log(2));
    }
```

Vorteil: Weniger oft addieren...


----------



## Oneixee5 (5. Jun 2021)

CyborgIstDoof hat gesagt.:


> hätte ich jetzt auch gesagt, aber es ginge auch mit einem Bitset der Länge n.
> 
> 
> ```
> ...


Ich sehe hier die "paarweise" Speicherung nicht oder übersehe ich was?


----------



## CyborgIstDoof (5. Jun 2021)

Oneixee5 hat gesagt.:


> Ich sehe hier die "paarweise" Speicherung nicht oder übersehe ich was?


ja, das Wort "paarweise verschieden". Das bedeutet einfach nur, es gibt keine doppelten Elemente. Aber ich bin kein Mathematicus, auch ich kenne die genauen Begrifflichkeiten nicht.


----------

