Deranged | Topcoder Archive

Problem Statement

A derangement of n numbers is a permutation of those numbers in which none of the numbers appears in its original place. For example, the numbers {1,2,3} can be deranged into {2,3,1} and {3,1,2}. We can modify this slightly for n numbers that are not necessarily distinct by saying that no number in the derangement can be in the place that a number of the same value was in in the original ordering. So the numbers {1,1,2,2,3} could be deranged into {2,2,1,3,1}, {2,2,3,1,1}, {2,3,1,1,2}, and {3,2,1,1,2}. Create a class Deranged with a function numDerangements that takes a int[] nums and return the number of derangements of nums.

Definition

Class:: Deranged
Method:: numDerangements
Parameters:: int[]
Returns:: long
Method signature:: long numDerangements(int[] nums)
(be sure your method is public)

Notes

The return value will fit in a 64-bit unsigned integer.

Constraints

nums will contain between 1 and 15 elements, inclusive.
nums will only contain values between 0 and the number of elements in nums - 1, inclusive.

Examples

```
{1,1,2,2,3}
```
```
Returns: 4
```
The example from above.
```
{0,0,0,1,1,1}
```
```
Returns: 1
```
The only derangement is {1,1,1,0,0,0}.
```
{0,0,0,1,1,1,1}
```
```
Returns: 0
```
There is no way to arrange the numbers such that no 1 is where a 1 was originally.

{0,0,0,0,0,0,0,1,1,1,1,1,1,1,2}

Returns: 14

```
{0,5,4,2,3,6,6}
```
```
Returns: 640
```

{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14}

Returns: 481066515734

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.