Count the number of arrays formed by rearranging elements such that one adjacent element is multiple of other
Given array A[] of size N (1 <= N <= 15), count all possible arrays formed by rearranging elements of A[] such that at least one of the following conditions is true for adjacent elements of that array:
- A[i] % A[i + 1] == 0
- A[i + 1] % A[i] == 0
The count can be a large, modulo answer with 109+ 7 before printing.
Examples:
Input: A[] = {2, 3, 6}
Output: 2
Explanation: {3, 6, 2} and {2, 6, 3} are two possible rearrangement of array A[] such that one of the required conditions satisfy for adjacent elements.Input: A[] = {1, 4, 3}
Output: 2
Explanation: {3, 1, 4} and {4, 1, 3} are two possible rearrangement of array A[] such that one of the required conditions satisfy for adjacent elements.
Approach: Implement the idea below to solve the problem
Bitmask Dynamic Programming can be used to solve this problem. The main concept of DP in the problem will be:
DP[i][j] represents count of arrangements which satisfy above conditions where i represents subset in form of bitmask and j represents last element of this subset so to check divisibility conditions when new element will be added in subset i.
Transition:
dp[i | (1 << (k – 1))][k] = (dp[i | (1 << (k – 1))][k] + dp[i][j])
here k is kth element of array A[] being added at the end of the subset i whose last element is j’th of array A[]
Steps were taken to solve the problem:
- Declaring DP[1 << N][N + 1] array.
- Initializing the base case by iterating over 0 to N – 1 as i, then set dp[1 << i][i + 1] = 1
- Iterating over all subsets from 1 to 2N as i and for each iteration
- Iterate from 1 to N as j if the j’th bit of subset i is not set then it means that jth element is not considered in the current submask, so we skip that iteration.
- Else, Iterate from 1 to N as k and for each iteration and check if the k’th bit is not in the current submask and last element j and k satisfy required condition, then update dp table according to transitions: dp[i | (1 << (k – 1))][k] = (dp[i | (1 << (k – 1))][k] + dp[i][j])
- After iterating over all the submasks, add dp[(1 << N) – 1][i] which represents count of arrangement of size N with last element i which satisfies the above conditions.
- Return ans.
Code to implement the approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // mod const int mod = 1e9 + 7; // Function to Count the number of arrays formed // by rearranging given array which satisfy following // condition int countOfArr( int A[], int N) { // DP array initalized with 0 vector<vector< int > > dp((1 << (N + 1)), vector< int >(N + 2, 0)); // base case for ( int i = 0; i < N; i++) dp[1 << i][i + 1] = 1; // iterating over all subsets for ( int i = 1; i < (1 << N); i++) { // if last element was picked was j from array A[] for ( int j = 1; j <= N; j++) { // if j'th element not present in current subset // i skip the iteration if (((1 << (j - 1)) & i) == 0) continue ; // tring to choose k'th element from array A[] for ( int k = 1; k <= N; k++) { // if k'th element of A is not visited and // last element j and current element k // satisfy the required condition update dp // according to transitions if (((1 << (k - 1)) & i) == 0 and (A[j - 1] % A[k - 1] == 0 or A[k - 1] % A[j - 1] == 0)) { dp[i | (1 << (k - 1))][k] = (dp[i | (1 << (k - 1))][k] + dp[i][j]) % mod; } } } } // variable to count all permutaions int ans = 0; // accumulating all arrangements of size N and last // element i for ( int i = 1; i <= N; i++) { ans = (ans + dp[(1 << N) - 1][i]) % mod; } // return the total count return ans; } // Driver Code int32_t main() { // Input int N = 3; int A[] = { 2, 3, 6 }; // Function Call cout << countOfArr(A, N) << endl; return 0; } |
Java
// Java code to implement the approach class GFG { // Function to Count the number of arrays formed // by rearranging given array which satisfy following // condition static int count_of_arr( int A[], int N) { // mod int mod = ( int ) (1e9 + 7 ); // DP array initialized with 0 int [][] dp = new int [ 1 << (N + 1 )][N + 2 ]; // base case for ( int i = 0 ; i < N; i++) { dp[ 1 << i][i + 1 ] = 1 ; } // iterating over all subsets for ( int i = 1 ; i < ( 1 << N); i++) { // if last element picked was j from array A[] for ( int j = 1 ; j <= N; j++) { // if j'th element not present in the current subset // skip the iteration if ((i & ( 1 << (j - 1 ))) == 0 ) { continue ; } // trying to choose k'th element from array A[] for ( int k = 1 ; k <= N; k++) { // if k'th element of A is not visited and // last element j and current element k // satisfy the required condition update dp // according to transitions if ((i & ( 1 << (k - 1 ))) == 0 && (A[j - 1 ] % A[k - 1 ] == 0 || A[k - 1 ] % A[j - 1 ] == 0 )) { dp[i | ( 1 << (k - 1 ))][k] = (dp[i | ( 1 << (k - 1 ))][k] + dp[i][j]) % mod; } } } } // variable to count all permutations int ans = 0 ; // accumulating all arrangements of size N and last // element i for ( int i = 1 ; i <= N; i++) { ans = (ans + dp[( 1 << N) - 1 ][i]) % mod; } // return the total count return ans; } // Driver Code public static void main(String[] args) { // Input int N = 3 ; int [] A = { 2 , 3 , 6 }; // Function Call System.out.println(count_of_arr(A, N)); } } |
Python3
# Python code to implement the approach # Function to Count the number of arrays formed # by rearranging given array which satisfy following # condition def count_of_arr(A, N): # mod mod = 10 * * 9 + 7 # DP array initalized with 0 dp = [[ 0 ] * (N + 2 ) for _ in range ( 1 << (N + 1 ))] # base case for i in range (N): dp[ 1 << i][i + 1 ] = 1 # iterating over all subsets for i in range ( 1 , 1 << N): # if last element was picked was j from array A[] for j in range ( 1 , N + 1 ): # if j'th element not present in current subset # i skip the iteration if not ( 1 << (j - 1 )) & i: continue # tring to choose k'th element from array A[] for k in range ( 1 , N + 1 ): # if k'th element of A is not visited and # last element j and current element k # satisfy the required condition update dp # according to transitions if not ( 1 << (k - 1 )) & i and (A[j - 1 ] % A[k - 1 ] = = 0 or A[k - 1 ] % A[j - 1 ] = = 0 ): dp[i | ( 1 << (k - 1 ))][k] = (dp[i | ( 1 << (k - 1 ))] [k] + dp[i][j]) % mod # variable to count all permutaions ans = 0 # accumulating all arrangements of size N and last # element i for i in range ( 1 , N + 1 ): ans = (ans + dp[( 1 << N) - 1 ][i]) % mod # return the total count return ans # Driver Code if __name__ = = "__main__" : # Input N = 3 A = [ 2 , 3 , 6 ] # Function Call print (count_of_arr(A, N)) |
C#
// C# code to implement the approach using System; class GFG { // mod const int mod = 1000000007; // Function to Count the number of arrays formed // by rearranging given array which satisfy following // condition static int countOfArr( int [] A, int N) { // DP array initialized with 0 var dp = new int [1 << (N + 1), N + 2]; // base case for ( int i = 0; i < N; i++) dp[1 << i, i + 1] = 1; // iterating over all subsets for ( int i = 1; i < (1 << N); i++) { // if last element was picked was j from array A[] for ( int j = 1; j <= N; j++) { // if j'th element not present in current subset // i skip the iteration if (((1 << (j - 1)) & i) == 0) continue ; // trying to choose k'th element from array A[] for ( int k = 1; k <= N; k++) { // if k'th element of A is not visited and // last element j and current element k // satisfy the required condition update dp // according to transitions if (((1 << (k - 1)) & i) == 0 && (A[j - 1] % A[k - 1] == 0 || A[k - 1] % A[j - 1] == 0)) { dp[i | (1 << (k - 1)), k] = (dp[i | (1 << (k - 1)), k] + dp[i, j]) % mod; } } } } // variable to count all permutations int ans = 0; // accumulating all arrangements of size N and last // element i for ( int i = 1; i <= N; i++) { ans = (ans + dp[(1 << N) - 1, i]) % mod; } // return the total count return ans; } // Driver Code static void Main() { // Input int N = 3; int [] A = { 2, 3, 6 }; // Function Call Console.WriteLine(countOfArr(A, N)); } } |
Javascript
// Function to Count the number of arrays formed // by rearranging given array which satisfy following // condition function countOfArr(A, N) { // mod const mod = 10**9 + 7; // DP array initialized with 0 const dp = Array.from({ length: 1 << (N + 1) }, () => Array(N + 2).fill(0)); // base case for (let i = 0; i < N; i++) { dp[1 << i][i + 1] = 1; } // iterating over all subsets for (let i = 1; i < 1 << N; i++) { // if last element was picked was j from array A[] for (let j = 1; j <= N; j++) { // if j'th element not present in the current subset // skip the iteration if (!((1 << (j - 1)) & i)) { continue ; } // trying to choose k'th element from array A[] for (let k = 1; k <= N; k++) { // if k'th element of A is not visited and // last element j and current element k // satisfy the required condition, update dp // according to transitions if ( !((1 << (k - 1)) & i) && (A[j - 1] % A[k - 1] === 0 || A[k - 1] % A[j - 1] === 0)) { dp[i | (1 << (k - 1))][k] = (dp[i | (1 << (k - 1))][k] + dp[i][j]) % mod; } } } } // variable to count all permutations let ans = 0; // accumulating all arrangements of size N and last // element i for (let i = 1; i <= N; i++) { ans = (ans + dp[(1 << N) - 1][i]) % mod; } // return the total count return ans; } // Driver Code // Input const N = 3; const A = [2, 3, 6]; // Function Call console.log(countOfArr(A, N)); |
2
Time Complexity: O(N2 * 2N), where N is the size of input array A[].
Auxiliary Space: O(N * 2N)