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 2Nas 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:

2

Time Complexity: O(N2* 2N), where N is the size of input array A[].
Auxiliary Space: O(N * 2N)