Find the Derangement of An Array
Problem
Count derangements of 1..n (permutations with no fixed point), modulo 10^9+7.
n = 32def find_derangement(n):
MOD = 10**9 + 7
a, b = 1, 0
for k in range(2, n + 1):
a, b = b, (k - 1) * (a + b) % MOD
return bfunction findDerangement(n) {
const MOD = 1000000007n;
let a = 1n, b = 0n;
for (let k = 2n; k <= BigInt(n); k++) [a, b] = [b, (k - 1n) * (a + b) % MOD];
return Number(b);
}int findDerangement(int n) {
long MOD = 1_000_000_007L, a = 1, b = 0;
for (int k = 2; k <= n; k++) { long c = (k - 1) * (a + b) % MOD; a = b; b = c; }
return (int) b;
}int findDerangement(int n) {
long MOD = 1e9 + 7, a = 1, b = 0;
for (int k = 2; k <= n; k++) { long c = (k - 1) * (a + b) % MOD; a = b; b = c; }
return (int) b;
}Explanation
A derangement is a way to shuffle 1..n so that no number stays in its own spot. Counting them directly is messy, but there is a clean recurrence that lets us build the count up step by step.
The formula is d(n) = (n - 1) * (d(n-1) + d(n-2)). The intuition: element n must go to one of n-1 other positions (say position k). Then either element k takes position n (leaving a derangement of the remaining n-2), or it does not (which behaves like a derangement of n-1). That gives the two terms inside the parentheses.
The base cases are d(1) = 0 (a single item can't move) and d(2) = 1 (only the swap works). We carry just two rolling values, a = d(n-2) and b = d(n-1), and update them in a loop, taking everything % MOD to keep numbers small.
Example: n = 3. Start with a = 1 (=d(2)), b = 0 (=d(1))... after the loop step for k = 3 we get d(3) = 2 * (1 + 0) = 2, matching the two valid shuffles [2,3,1] and [3,1,2].
Because it's a single pass keeping two numbers, it runs in O(n) time and O(1) space.