Đề bài
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.
Ràng buộc
0 ≤ n ≤ 20
Ví dụ
Đầu vào:
n = 3
Kết quả mong đợi:
expected = 2
Đầu vào:
long long n = 3;
Kết quả mong đợi:
long long expected = 2;
Đầu vào:
long n = 3;
Kết quả mong đợi:
long expected = 2;
Giải thích
For items A, B, C only BCA and CAB move every item, so the answer is 2.
Đầu vào:
n = 4
Kết quả mong đợi:
expected = 9
Đầu vào:
long long n = 4;
Kết quả mong đợi:
long long expected = 9;
Đầu vào:
long n = 4;
Kết quả mong đợi:
long expected = 9;
Giải thích
D(4) = 3 × (D(3) + D(2)) = 3 × (2 + 1) = 9.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Start from D(0) = 1 and D(1) = 0.
Gợi ý 2
Each next value uses the two previous ones and the current n.
Gợi ý 3
Only the last two values are needed at any time.
Độ phức tạp mong đợi
O(n) time, O(1) extra space
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.