Deranged
SRM 176 · 2003-12-22 · by Running Wild
SRM 176 · 2003-12-22 · by Running Wild · Advanced Math
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.
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,1,2,2,3}
Returns: 4
The example from above.
1)
{0,0,0,1,1,1}
Returns: 1
The only derangement is {1,1,1,0,0,0}.
2)
{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.
3)
{0,0,0,0,0,0,0,1,1,1,1,1,1,1,2}
Returns: 14
4)
{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14}
Returns: 481066515734
Submissions are judged against all 37 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class Deranged with a public method long long numDerangements(vector<int> nums) · 37 test cases · 2 s / 256 MB per case