Knobelaufgabe Java

[gast1234]

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]

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

 

[CyborgIstDoof]

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]

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...

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

 

[CyborgIstDoof]

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.