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