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 |
| 0) | |
| | |
| 1) | |
| | | Returns: 1 | | The only derangement is {1,1,1,0,0,0}. |
|
|
| 2) | |
| | | Returns: 0 | | There is no way to arrange the numbers such that no 1 is where a 1 was originally. |
|
|
| 3) | |
| | {0,0,0,0,0,0,0,1,1,1,1,1,1,1,2} |
| Returns: 14 | |
|
| 4) | |
| | |
| 5) | |
| | {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14} |
| Returns: 481066515734 | |
|