Mittel 0 gelöst 0% Erfolgsquote

Derangements

Count the arrangements of n items where nothing stays in its original place.

Das lernst du

  • Turn a counting argument into a recurrence
  • Iterate a recurrence from base cases
  • Handle the n = 0 and n = 1 cases

Problem

Übersetzung anzeigen

Five friends put their hats in a pile and each takes one back at random. In how many ways can it happen that nobody gets their own hat? An arrangement of n items in which no item stays in its original position is called a derangement. The counts start 1, 0, 1, 2, 9, 44 and follow D(n) = (n − 1) × (D(n − 1) + D(n − 2)).

Implement derangements(n).

Input

n: The number of items.

Output

Return the number of derangements of n items. D(0) is 1 (the empty arrangement moves nothing that could stay) and D(1) is 0.

Einschränkungen

0 ≤ n ≤ 20

Beispiele

Beispiel 1
Eingabe:
n = 3

Erwartete Ausgabe:
expected = 2
Eingabe:
long long n = 3;

Erwartete Ausgabe:
long long expected = 2;
Eingabe:
long n = 3;

Erwartete Ausgabe:
long expected = 2;

Erläuterung

For items A, B, C only BCA and CAB move every item, so the answer is 2.

Beispiel 2
Eingabe:
n = 4

Erwartete Ausgabe:
expected = 9
Eingabe:
long long n = 4;

Erwartete Ausgabe:
long long expected = 9;
Eingabe:
long n = 4;

Erwartete Ausgabe:
long expected = 9;

Erläuterung

D(4) = 3 × (D(3) + D(2)) = 3 × (2 + 1) = 9.

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Start from D(0) = 1 and D(1) = 0.

Hinweis 2

Each next value uses the two previous ones and the current n.

Hinweis 3

Only the last two values are needed at any time.

Erwartete Komplexität

O(n) time, O(1) extra space

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.