Count the Derangements — Solution & Editorial

Back to the Problem

Recurrence D_n = (n−1)(D_n−1 + D_n−2) with D₀ = 1, D₁ = 0.

Complexity: O(N)