Problema
Cinco amigos deixam os chapéus em uma pilha e cada um pega um de volta ao acaso. De quantas maneiras pode acontecer de ninguém pegar o próprio chapéu? Uma permutação de n itens em que nenhum item fica na posição original é chamada de permutação caótica (em inglês, derangement). As quantidades começam com 1, 0, 1, 2, 9, 44 e seguem D(n) = (n − 1) × (D(n − 1) + D(n − 2)).
Implemente derangements(n).
Entrada
n: o número de itens.
Saída
Retorne o número de permutações caóticas de n itens. D(0) é 1 (a permutação vazia não tira nada do lugar) e D(1) é 0.
Restrições
0 ≤ n ≤ 20
Exemplos
Entrada:
n = 3
Saída esperada:
expected = 2
Entrada:
long long n = 3;
Saída esperada:
long long expected = 2;
Entrada:
long n = 3;
Saída esperada:
long expected = 2;
Explicação
Para os itens A, B, C, só BCA e CAB tiram todos do lugar, então a resposta é 2.
Entrada:
n = 4
Saída esperada:
expected = 9
Entrada:
long long n = 4;
Saída esperada:
long long expected = 9;
Entrada:
long n = 4;
Saída esperada:
long expected = 9;
Explicação
D(4) = 3 × (D(3) + D(2)) = 3 × (2 + 1) = 9.
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Comece com D(0) = 1 e D(1) = 0.
Dica 2
Cada novo valor usa os dois anteriores e o n atual.
Dica 3
A cada momento só os dois últimos valores são necessários.
Complexidade esperada
tempo O(n), espaço extra O(1)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.