Problem Description

You are given a 0-indexed integer array nums containing n distinct positive integers. Your task is to find how many permutations of this array are "special."

A permutation is considered special if it satisfies the following condition:

• For every pair of adjacent elements in the permutation (at positions i and i+1), at least one element must be divisible by the other. In other words, for all indexes 0 <= i < n - 1, either nums[i] % nums[i+1] == 0 or nums[i+1] % nums[i] == 0.

For example, if we have a permutation [a, b, c], it would be special if:

• Either a divides b or b divides a, AND
• Either b divides c or c divides b

The problem asks you to count the total number of such special permutations. Since this count could be very large, you should return the result modulo 10^9 + 7.

The solution uses state compression dynamic programming, where f[i][j] represents the number of ways to form valid sequences when:

• i is a bitmask indicating which numbers have been used (bit k is 1 if nums[k] is used)
• j is the index of the last number added to the sequence

The transition works by checking if adding number at index j to a state can form a valid sequence, considering the divisibility constraint with the previously added number.

Intuition

When we need to count permutations with specific constraints, we need to think about how to build valid permutations step by step. The key insight here is that we care about two things: which numbers we've already used, and what the last number we placed was (since it determines what can come next).

Since the array size is at most 14, we can use bitmask to represent which numbers have been selected. This is feasible because 2^14 = 16384 states is manageable. Each bit in the mask tells us whether a specific number has been used or not.

The critical observation is that in a valid special permutation, every adjacent pair must satisfy the divisibility condition. This means when we're building the permutation, we only need to remember the last number we placed - it's the only one that affects what we can place next.

This leads us to dynamic programming with states f[mask][last], where:

• mask represents which numbers we've used so far (as a bitmask)
• last is the index of the last number we added to our sequence

To build larger permutations, we can extend smaller valid sequences. If we want to add number at index j to our current sequence, we need to:

1. Make sure j hasn't been used yet (check if bit j in mask is 0)
2. Make sure nums[j] satisfies the divisibility condition with the last number in our sequence

The base case is when we start with just one number - any single number forms a valid sequence of length 1, so f[2^j][j] = 1.

For larger sequences, we compute f[i][j] by looking at all possible previous states. We consider the state where number j wasn't included yet (that's i ^ (1 << j)), and sum up all the ways to reach that state with different last numbers k, as long as nums[k] and nums[j] satisfy the divisibility requirement.

The final answer is the sum of f[2^n - 1][j] for all possible last positions j, where 2^n - 1 represents the state where all numbers have been used.

Learn more about Dynamic Programming and Bitmask patterns.

Solution Approach

The solution implements state compression dynamic programming as described in the reference approach. Let's walk through the implementation step by step:

1. Initialization:

mod = 10**9 + 7
n = len(nums)
m = 1 << n  # m = 2^n, total number of possible states
f = [[0] * n for _ in range(m)]

We create a 2D DP table f where f[i][j] represents the number of valid sequences when state i indicates which numbers are used, and j is the index of the last number added.

2. Main DP Loop:

for i in range(1, m):
    for j, x in enumerate(nums):

We iterate through all possible states i from 1 to 2^n - 1, and for each state, we check each position j as a potential last element.

3. Check if position j is included in state i:

if i >> j & 1:

This checks if the j-th bit of i is set to 1, meaning nums[j] is included in the current state.

4. Calculate previous state:

ii = i ^ (1 << j)

This removes the j-th bit from state i to get the previous state ii (before adding nums[j]).

5. Base Case:

if ii == 0:
    f[i][j] = 1
    continue

If ii == 0, it means we only have one number selected (just nums[j]), which always forms a valid sequence of length 1.

6. State Transition:

for k, y in enumerate(nums):
    if x % y == 0 or y % x == 0:
        f[i][j] = (f[i][j] + f[ii][k]) % mod

For non-base cases, we enumerate all possible previous last positions k. If nums[j] (denoted as x) and nums[k] (denoted as y) satisfy the divisibility condition (x % y == 0 or y % x == 0), we can extend the sequence ending at k by adding j. We add f[ii][k] to f[i][j].

Note that the condition implicitly checks if k was in the previous state ii because f[ii][k] would be 0 if position k wasn't included in state ii.

7. Final Answer:

return sum(f[-1]) % mod

The answer is the sum of all f[2^n - 1][j] for all possible last positions j. Here f[-1] refers to f[m-1] which is f[2^n - 1], representing the state where all numbers have been used.

The time complexity is O(2^n × n^2) where we have 2^n states, and for each state, we check n positions as the last element, and for each position, we check up to n previous positions. The space complexity is O(2^n × n) for the DP table.

Example Walkthrough

Let's walk through a small example with nums = [2, 4, 8] to illustrate how the dynamic programming solution works.

Step 1: Setup

• n = 3, so we have m = 2^3 = 8 possible states
• States are represented as 3-bit numbers: 000 to 111
• Initialize DP table f[8][3] with all zeros

Step 2: Process each state

Let's trace through some key states:

State i = 001 (binary) = 1 (decimal): Only nums[0] = 2 is selected

• Check position j = 0: Bit 0 is set, so nums[0] is included
• Previous state ii = 001 ^ 001 = 000 (empty)
• Since ii == 0, this is a base case: f[1][0] = 1
• Result: We have 1 way to form a sequence with just [2]

State i = 010 (binary) = 2 (decimal): Only nums[1] = 4 is selected

• Check position j = 1: Bit 1 is set, so nums[1] is included
• Previous state ii = 010 ^ 010 = 000 (empty)
• Base case: f[2][1] = 1
• Result: We have 1 way to form a sequence with just [4]

State i = 011 (binary) = 3 (decimal): Both nums[0] = 2 and nums[1] = 4 are selected

• Check position j = 0 (last element is 2):

  • Previous state ii = 011 ^ 001 = 010 (only 4 is selected)
  • Check if we can append 2 after 4: 2 % 4 = 2 (not 0), 4 % 2 = 0 ✓
  • Add transitions: f[3][0] += f[2][1] = 0 + 1 = 1
  • Result: Sequence [4, 2] is valid

• Check position j = 1 (last element is 4):

  • Previous state ii = 011 ^ 010 = 001 (only 2 is selected)
  • Check if we can append 4 after 2: 4 % 2 = 0 ✓
  • Add transitions: f[3][1] += f[1][0] = 0 + 1 = 1
  • Result: Sequence [2, 4] is valid

State i = 111 (binary) = 7 (decimal): All three numbers are selected

• Check position j = 0 (last element is 2):

  • Previous state ii = 111 ^ 001 = 110 (4 and 8 are selected)
  • Check transitions from f[110][1] (last was 4) and f[110][2] (last was 8)
  • Neither 4→2 nor 8→2 satisfy divisibility, so f[7][0] = 0

• Check position j = 1 (last element is 4):

  • Previous state ii = 111 ^ 010 = 101 (2 and 8 are selected)
  • Check if 2→4 works: 4 % 2 = 0 ✓, so add f[101][0]
  • Check if 8→4 works: 4 % 8 = 4 (not 0), 8 % 4 = 0 ✓, so add f[101][2]

• Check position j = 2 (last element is 8):

  • Previous state ii = 111 ^ 100 = 011 (2 and 4 are selected)
  • Check if 2→8 works: 8 % 2 = 0 ✓, so add f[011][0]
  • Check if 4→8 works: 8 % 4 = 0 ✓, so add f[011][1]
  • f[7][2] = f[011][0] + f[011][1] = 1 + 1 = 2

Step 3: Final Answer Sum all ways to form complete permutations: f[7][0] + f[7][1] + f[7][2]

After computing all states, the valid special permutations are:

• [2, 4, 8]: 2 divides 4, 4 divides 8 ✓
• [4, 2, 8]: 4 divides by 2, 2 divides 8 ✓

Total: 2 special permutations

Solution Implementation

Time and Space Complexity

Time Complexity: O(n^2 × 2^n)

The algorithm uses dynamic programming with bitmask to track which elements have been used. The outer loop iterates through all possible masks from 1 to 2^n - 1, giving us O(2^n) iterations. For each mask i, we iterate through all n elements to check if they can be the last element in the current permutation (the j loop). For each valid position j, we then iterate through all n elements again (the k loop) to find compatible previous elements where either x % y == 0 or y % x == 0. This gives us O(n × n) = O(n^2) operations for each mask state. Therefore, the total time complexity is O(2^n × n^2) or O(n^2 × 2^n).

Space Complexity: O(n × 2^n)

The algorithm uses a 2D DP table f with dimensions m × n, where m = 2^n (representing all possible subsets of elements) and n is the number of elements. Each cell f[i][j] stores the count of valid permutations for mask i ending with element at index j. This requires O(2^n × n) or O(n × 2^n) space to store the DP table.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Divisibility Check for Previous Elements

One of the most common mistakes is forgetting to verify that the previous element was actually part of the previous state before adding its contribution. In the transition loop:

for prev_idx, prev_val in enumerate(nums):
    if last_val % prev_val == 0 or prev_val % last_val == 0:
        dp[mask][last_idx] = (dp[mask][last_idx] + dp[prev_mask][prev_idx]) % MOD

The Problem: This code adds dp[prev_mask][prev_idx] even when prev_idx wasn't actually in prev_mask. While this might seem to work because dp[prev_mask][prev_idx] would be 0 if prev_idx wasn't used, it's inefficient and conceptually incorrect.

The Solution: Explicitly check if the previous element was in the previous state:

for prev_idx, prev_val in enumerate(nums):
    # Check if prev_idx was in the previous state
    if (prev_mask >> prev_idx & 1) and (last_val % prev_val == 0 or prev_val % last_val == 0):
        dp[mask][last_idx] = (dp[mask][last_idx] + dp[prev_mask][prev_idx]) % MOD

2. Forgetting the Modulo Operation

Another frequent mistake is applying modulo only at the final return statement:

# Incorrect: might cause integer overflow in languages with fixed integer sizes
dp[mask][last_idx] = dp[mask][last_idx] + dp[prev_mask][prev_idx]

# Then only at the end:
return sum(dp[-1]) % MOD

The Problem: While Python handles arbitrarily large integers, accumulating values without modulo can lead to unnecessarily large intermediate values, affecting performance. In other languages, this would cause integer overflow.

The Solution: Apply modulo during each addition:

dp[mask][last_idx] = (dp[mask][last_idx] + dp[prev_mask][prev_idx]) % MOD

3. Off-by-One Error in Bit Manipulation

A subtle but critical error occurs when checking or setting bits:

# Incorrect: using wrong bit position
if mask >> (last_idx + 1) & 1:  # Wrong! Checking bit at position last_idx + 1

# Or when creating prev_mask:
prev_mask = mask ^ (1 << (last_idx - 1))  # Wrong! Toggling wrong bit

The Problem: Since we're using 0-indexed arrays, bit position i corresponds to nums[i]. Any offset will check/modify the wrong element.

The Solution: Use the index directly without any offset:

if mask >> last_idx & 1:  # Correct: check bit at position last_idx
prev_mask = mask ^ (1 << last_idx)  # Correct: toggle bit at position last_idx

4. Starting Loop from Wrong State

# Incorrect: starting from 0
for mask in range(total_states):  # Includes mask = 0

# Or incorrect: missing state 1
for mask in range(2, total_states):  # Skips single-element states

The Problem: State 0 represents an empty subset (no elements selected), which isn't meaningful for our problem. We need to start from state 1 (at least one element selected).

The Solution: Start the loop from 1:

for mask in range(1, total_states):  # Correct: starts from state 1