TopCoder Statistics - Problem Statement

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,1,2,3,4,5,6,7,8,9,10,11,12,13,14}

Returns: 481066515734
{1,4,4,2,0}

Returns: 12
{7,8,5,10,11,8,5,10,7,8,9,6}

Returns: 1151487
{6,7,8,9,2,11,8,1,2,11,0,5}

Returns: 12563896
{4,6,9,1,10,5,3,7,7,4,7,6,11}

Returns: 38707344
{4,12,6,4,11,12,12,2,1,11,9,0,4}

Returns: 8935756
{6,1,4,3,6,1,8,9,4,3}

Returns: 33905
{4,5,10,3,4,1,6,3,0,9,6,11}

Returns: 12563896
{3,8,5,2,5,8,9,6,5,8}

Returns: 8193
{2,1,6,9,0,7,2,5,8,5}

Returns: 209581
{2,3,0,1,6,7,4,5}

Returns: 14833
{0,1,6,7,4,5,2,3}

Returns: 14833
{7,8,10,8,8,6,3,10,2,4,4,1,5}

Returns: 38707344
{6,4,3,0,13,3,6,0,1,0,14,5,10,12,14}

Returns: 4053826542
{0}

Returns: 0
{8,8,0,9,10,6,8,5,3,8,0}

Returns: 48480
{13,4,10,8,8,2,2,3,9,0,5,10,11,11,1}

Returns: 16783469910
{5,0,6,2,3,6,3,5,4,1,3}

Returns: 204684
{0,1}

Returns: 1
{3,7,12,10,5,2,7,8,7,11,4,11,10}

Returns: 38707344
{1,4,3,3,9,1,9,1,0,10,7}

Returns: 204684
{4,8,6,10,1,9,7,1,7,2,10,1,9}

Returns: 16522632
{2,3,0,1,6,7,4,5}

Returns: 14833
{0,9,6,7,0,9,10,11,4,5,2,3}

Returns: 30173825
{5,12,4,1,3,12,8,12,12,0,1,12,9}

Returns: 682800
{11,0,5,10,7,8,9,2,3,4,1,10}

Returns: 72755370
{8,1,10,3,4,9,6,7,8,1,6,11}

Returns: 12563896
{3,1,2,0,3}

Returns: 12
{0,5,4,2,3,6,6}

Returns: 640
{9,2,0,3,14,14,1,6,12,8,13,7,11,8,0}

Returns: 38727700100
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

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

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

Returns: 481066515734

Statistics

Problem Statement for "Deranged"

Problem Statement

Definition

Notes

Constraints

Examples