Problema
Cinco amigos dejan sus sombreros en un montón y cada uno toma uno al azar. ¿De cuántas maneras puede ocurrir que nadie recupere el suyo? Una ordenación de n elementos en la que ningún elemento queda en su posición original se llama desarreglo. Las cantidades empiezan 1, 0, 1, 2, 9, 44 y cumplen D(n) = (n − 1) × (D(n − 1) + D(n − 2)).
Implementa derangements(n).
Entrada
n: la cantidad de elementos.
Salida
Devuelve la cantidad de desarreglos de n elementos. D(0) es 1 (la ordenación vacía no deja nada en su sitio) y D(1) es 0.
Restricciones
0 ≤ n ≤ 20
Ejemplos
Entrada:
n = 3
Salida esperada:
expected = 2
Entrada:
long long n = 3;
Salida esperada:
long long expected = 2;
Entrada:
long n = 3;
Salida esperada:
long expected = 2;
Explicación
Con los elementos A, B, C, solo BCA y CAB mueven todos los elementos, así que la respuesta es 2.
Entrada:
n = 4
Salida esperada:
expected = 9
Entrada:
long long n = 4;
Salida esperada:
long long expected = 9;
Entrada:
long n = 4;
Salida esperada:
long expected = 9;
Explicación
D(4) = 3 × (D(3) + D(2)) = 3 × (2 + 1) = 9.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Empieza con D(0) = 1 y D(1) = 0.
Pista 2
Cada valor nuevo usa los dos anteriores y el n actual.
Pista 3
En cada momento solo necesitas los dos últimos valores.
Complejidad esperada
tiempo O(n), espacio extra O(1)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.