Medium 0 solved 0% acceptance

Derangements

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

What you'll learn

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

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.

Constraints

0 ≤ n ≤ 20

Examples

Example 1
Input:
n = 3

Expected output:
expected = 2
Input:
long long n = 3;

Expected output:
long long expected = 2;
Input:
long n = 3;

Expected output:
long expected = 2;

Explanation

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

Example 2
Input:
n = 4

Expected output:
expected = 9
Input:
long long n = 4;

Expected output:
long long expected = 9;
Input:
long n = 4;

Expected output:
long expected = 9;

Explanation

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

How to approach it

Try on your own first, then open one hint at a time.

Hint 1

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

Hint 2

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

Hint 3

Only the last two values are needed at any time.

Expected complexity

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

References

This challenge is adapted for CodeUtility. Follow the statement and constraints above.

The best passing solution of each coder. Faster, smaller and better-reviewed solutions rank higher.

No passing solutions yet. Solve it to take first place.

Learn from others

Community solutions

No published solutions yet. Solve this challenge to share the first one.