Trung bình 0 đã giải Tỷ lệ chấp nhận 0%

Derangements

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

Bạn sẽ học được gì

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

Đề bài

Xem bản dịch

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ụ

Ví dụ 1
Đầ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.

Ví dụ 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.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.