Given an array arr[] of N numbers (N ≤ 20), the task is to find the number of Derangements of the array where array elements can be repeated.
A derangement is a permutation of N elements, such that no element appears in its original position. For example, a derangement of {0, 1, 2, 3} is {2, 3, 1, 0}.
Examples:
Input: arr[] = {0, 0, 1}
Output: 0
Explanation: All permutations of the array are – {0, 0, 1}, {0, 1, 0} and{1, 0, 0}.
In each permutation, there is atleast one number which is placed in the same position as in the input array.
Hence the answer is 0.Input: arr[] = {1, 1, 0, 0}
Output: 1
Explanation: The only derangement is {0, 0, 1, 1}Input: arr[] = {1, 2, 2, 3, 3}
Output: 4
Explanation: The derangements are {2, 3, 3, 1, 2}, {2, 3, 3, 2, 1}, {3, 3, 1, 2, 2} and {3, 1, 3, 2, 2}
Naive Approach: The simplest approach to solve this problem is to generate all possible permutations and for each permutation, check if all the elements are not placed in their original position. If found to be true, then increment the count. Finally, print the count.
Time Complexity: O(N! * N)
Auxiliary Space: O(N)
Efficient Approach: The above approach can also be optimized using dynamic programming and bitmasking as it has overlapping subproblems and optimal substructure. The idea to solve this problem is based on the following observations:
- For each index of Arr[] the idea is to choose a not selected array element of Arr[] and using bitmasking to keep track of the already selected elements of Arr[]. The selected element must also be not equal to the current element to ensure derangement.
- dp(i, mask) stores the result from the ‘i’th position till the end, with bitmask ‘mask’ denoting the already selected elements of array Arr[] till the ‘i-1’th position.
- Since the current position can be determined by the count of set bits of mask, reduce dp(i, mask) to dp(mask).
- Then the transition from one state to another state can be defined as:
- For all j in the range [0, N – 1]:
- If the jth bit of mask is not set and if A[i] != A[j], then, dp(i, mask) += dp(i + 1, mask|(1<<j)).
Follow the steps below to solve the problem:
- Define a dp array of size (1 << N) and initialize it with -1 to store all dp states.
- Define a recursive function say countDerangements(i, mask) to count the number of derangements
- Base case, if i is equal to N then a valid derangement has been constructed.
- If dp[mask] is not equal to -1 i.e already visited then return dp[mask].
- Iterate over the range [0, N-1] using variable j and in each iteration, if jth bit in the mask is not set and if A[i] != A[j], then,
- Update dp[mask] as dp[mask] = dp[mask] + countDerangements (i+1, mask | (<< j)).
- Finally, return dp[mask].
- If any number is repeated more than once, then the answer returned has to be divided by the frequency of that number because the same number swapped in different positions will result in the same derangement.
- Hence, check for the frequency of all numbers and divide the answer by the frequency of a number if it is greater than 1.
- This will be the final answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Declaring a dp array long long dp[1 << 20]; // Function to return // the factorial of a number long long factorial( int n) { long long fact = 1; for ( int i = 2; i <= n; ++i) { fact *= i; } return fact; } // Function to count the // Number of derangements long long countDerangements( int i, int mask, int n, int A[]) { // If all the numbers are placed, // then return 1. if (mask == (1 << n) - 1) { return 1; } // If the state has already been computed, // then return it if (dp[mask] != -1) { return dp[mask]; } dp[mask] = 0; // Check for all possible numbers // that can be placed in // the current position 'i'. for ( int j = 0; j < n; ++j) { // If the current element arr[j] // Is not yet selected //(bit 'j' is unset in mask), // And if arr[i]!= arr[j] //(to ensure derangement). if (!(mask & (1 << j)) and (A[i] != A[j])) { // Set the bit 'j' in mask and // Call the function // For index 'i + 1'. dp[mask] += countDerangements( i + 1, mask | (1 << j), n, A); } } // Return dp[mask] return dp[mask]; } // Utility Function to count // The number of derangements long long UtilCountDerangements( int A[], int N) { // Initializing the dp array with -1. memset (dp, -1, sizeof dp); // HashMap to store the frequency // of each number. map< int , int > frequencyMap; for ( int i = 0; i < N; ++i) { ++frequencyMap[A[i]]; } // Function call and storing // The return value in 'ans'. long long ans = countDerangements(0, 0, N, A); // Iterating through the HashMap for ( auto itr : frequencyMap) { // Frequency of current number int times = itr.second; // If it occurs more than 1 time, // divide the answer by its frequency. if (times > 1) { ans /= factorial(times); } } return ans; } // Driver code int main() { // Input array int arr[] = { 1, 2, 2, 3, 3 }; // Size of array int N = sizeof (arr) / sizeof (arr[0]); cout << UtilCountDerangements(arr, N); return 0; } |
Java
// Java program to implement the approach import java.util.*; public class Main { // Declaring a dp array static int [] dp = new int [ 1 << 20 ]; // Function to return // the factorial of a number static int factorial( int n) { int fact = 1 ; for ( int i = 2 ; i <= n; ++i) { fact *= i; } return fact; } // Function to count the // Number of derangements static int countDerangements( int i, int mask, int n, int [] A) { // If all the numbers are placed, // then return 1. if (mask == ( 1 << n) - 1 ) { return 1 ; } // If the state has already been computed, // then return it if (dp[mask] != - 1 ) { return dp[mask]; } dp[mask] = 0 ; // Check for all possible numbers // that can be placed in // the current position 'i'. for ( int j = 0 ; j < n; ++j) { // If the current element arr[j] // Is not yet selected //(bit 'j' is unset in mask), // And if arr[i]!= arr[j] //(to ensure derangement). if ((mask & ( 1 << j)) == 0 && (A[i] != A[j])) { // Set the bit 'j' in mask and // Call the function // For index 'i + 1'. dp[mask] += countDerangements( i + 1 , mask | ( 1 << j), n, A); } } // Return dp[mask] return dp[mask]; } // Utility Function to count // The number of derangements static int UtilCountDerangements( int [] A, int N) { // Initializing the dp array with -1. for ( int i = 0 ;i<( 1 << 20 ); i++) { dp[i]=- 1 ; } // HashMap to store the frequency // of each number. HashMap<Integer, Integer> frequencyMap = new HashMap<Integer, Integer>(); for ( int i = 0 ; i < N; i++) { // Counting freq of each element if (frequencyMap.containsKey(A[i])){ frequencyMap.put(A[i], frequencyMap.get(A[i])+ 1 ); } else { frequencyMap.put(A[i], 1 ); } } // Function call and storing // The return value in 'ans'. int ans = countDerangements( 0 , 0 , N, A); // Iterating through the HashMap for (Map.Entry<Integer,Integer> itr : frequencyMap.entrySet()) { // Frequency of current number int times = itr.getValue(); // If it occurs more than 1 time, // divide the answer by its frequency. if (times > 1 ) { ans /= factorial(times); } } return ans; } // Driver code public static void main(String[] args) { // Input array int [] arr = { 1 , 2 , 2 , 3 , 3 }; // Size of array int N = arr.length; System.out.println( UtilCountDerangements(arr, N)); } } // This code is contributed by code_hunt. |
Python3
# Python program for the above approach # Declaring a dp array dp = [ - 1 ] * ( 1 << 20 ) # Function to return # the factorial of a number def factorial(n): fact = 1 for i in range ( 2 ,n + 1 ): fact * = i return fact # Function to count the # Number of derangements def countDerangements(i,mask,n, A): # If all the numbers are placed, # then return 1. if (mask = = ( 1 << n) - 1 ): return 1 # If the state has already been computed, # then return it if (dp[mask] ! = - 1 ): return dp[mask] dp[mask] = 0 # Check for all possible numbers # that can be placed in # the current position 'i'. for j in range (n): # If the current element arr[j] # Is not yet selected #(bit 'j' is unset in mask), # And if arr[i]!= arr[j] #(to ensure derangement). if (mask & ( 1 << j) = = 0 and (A[i] ! = A[j])): # Set the bit 'j' in mask and # Call the function # For index 'i + 1'. dp[mask] + = countDerangements(i + 1 , mask | ( 1 << j), n, A) # Return dp[mask] return dp[mask] # Utility Function to count # The number of derangements def UtilCountDerangements(A,N): # HashMap to store the frequency # of each number. frequencyMap = {} for i in range (N): if A[i] in frequencyMap: frequencyMap[A[i]] = frequencyMap[A[i]] + 1 else : frequencyMap[A[i]] = 1 # Function call and storing # The return value in 'ans'. ans = countDerangements( 0 , 0 , N, A) # Iterating through the HashMap for key,value in frequencyMap.items(): # Frequency of current number times = value # If it occurs more than 1 time, # divide the answer by its frequency. if (times > 1 ): ans = ans / / factorial(times) return ans # Driver code # Input array arr = [ 1 , 2 , 2 , 3 , 3 ] # Size of array N = len (arr) print (UtilCountDerangements(arr, N)) # This code is contributed by shinjanpatra. |
C#
// C# program of the above approach using System; using System.Collections.Generic; class GFG { // Declaring a dp array static int [] dp = new int [1 << 20]; // Function to return // the factorial of a number static int factorial( int n) { int fact = 1; for ( int i = 2; i <= n; ++i) { fact *= i; } return fact; } // Function to count the // Number of derangements static int countDerangements( int i, int mask, int n, int [] A) { // If all the numbers are placed, // then return 1. if (mask == (1 << n) - 1) { return 1; } // If the state has already been computed, // then return it if (dp[mask] != -1) { return dp[mask]; } dp[mask] = 0; // Check for all possible numbers // that can be placed in // the current position 'i'. for ( int j = 0; j < n; ++j) { // If the current element arr[j] // Is not yet selected //(bit 'j' is unset in mask), // And if arr[i]!= arr[j] //(to ensure derangement). if ((mask & (1 << j)) == 0 && (A[i] != A[j])) { // Set the bit 'j' in mask and // Call the function // For index 'i + 1'. dp[mask] += countDerangements( i + 1, mask | (1 << j), n, A); } } // Return dp[mask] return dp[mask]; } // Utility Function to count // The number of derangements static int UtilCountDerangements( int [] A, int N) { // Initializing the dp array with -1. for ( int i = 0;i<(1 << 20); i++) { dp[i]=-1; } // HashMap to store the frequency // of each number. Dictionary< int , int > frequencyMap = new Dictionary< int , int >(); for ( int i = 0; i < N; i++) { if (frequencyMap.ContainsKey(A[i])){ frequencyMap[A[i]] = frequencyMap[A[i]] + 1; } else { frequencyMap.Add(A[i], 1); } } // Function call and storing // The return value in 'ans'. int ans = countDerangements(0, 0, N, A); // Iterating through the HashMap foreach (KeyValuePair< int , int > itr in frequencyMap) { // Frequency of current number int times = itr.Value; // If it occurs more than 1 time, // divide the answer by its frequency. if (times > 1) { ans /= factorial(times); } } return ans; } // Driver Code public static void Main() { // Input array int [] arr = { 1, 2, 2, 3, 3 }; // Size of array int N = arr.Length; Console.Write( UtilCountDerangements(arr, N)); } } // This code is contributed by sanjoy_62. |
Javascript
<script> // JavaScript code for the above approach // Declaring a dp array let dp = new Array(1 << 20).fill(-1); // Function to return // the factorial of a number function factorial(n) { let fact = 1; for (let i = 2; i <= n; ++i) { fact *= i; } return fact; } // Function to count the // Number of derangements function countDerangements(i, mask, n, A) { // If all the numbers are placed, // then return 1. if (mask == (1 << n) - 1) { return 1; } // If the state has already been computed, // then return it if (dp[mask] != -1) { return dp[mask]; } dp[mask] = 0; // Check for all possible numbers // that can be placed in // the current position 'i'. for (let j = 0; j < n; ++j) { // If the current element arr[j] // Is not yet selected //(bit 'j' is unset in mask), // And if arr[i]!= arr[j] //(to ensure derangement). if (!(mask & (1 << j)) && (A[i] != A[j])) { // Set the bit 'j' in mask and // Call the function // For index 'i + 1'. dp[mask] += countDerangements( i + 1, mask | (1 << j), n, A); } } // Return dp[mask] return dp[mask]; } // Utility Function to count // The number of derangements function UtilCountDerangements(A, N) { // Initializing the dp array with -1 // HashMap to store the frequency // of each number. let frequencyMap = new Map(); for (let i = 0; i < N; ++i) { if (frequencyMap.has(A[i])) { frequencyMap.set(A[i], frequencyMap.get(A[i]) + 1) } else { frequencyMap.set(A[i], 1) } } // Function call and storing // The return value in 'ans'. let ans = countDerangements(0, 0, N, A); // Iterating through the HashMap for (let [key, val] of frequencyMap) { // Frequency of current number let times = val; // If it occurs more than 1 time, // divide the answer by its frequency. if (times > 1) { ans /= factorial(times); } } return ans; } // Driver code // Input array let arr = [1, 2, 2, 3, 3]; // Size of array let N = arr.length; document.write(UtilCountDerangements(arr, N)); // This code is contributed by Potta Lokesh </script> |
4
Time Complexity: O(N * 2N)
Auxiliary Space: O(2N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!