2741. Special Permutations - Solution

The problem

You are given a 0-indexed integer array nums containing n distinct positive integers. A permutation of nums is called special if:

For all indexes 0 <= i < n - 1, either nums[i] % nums[i+1] == 0 or nums[i+1] % nums[i] == 0.

Return the total number of special permutations. As the answer could be large, return it modulo 10⁹+ 7.

Example 1:

Input: nums = [2,3,6]
Output: 2
Explanation: [3,6,2] and [2,6,3] are the two special permutations of nums.

Example 2:

Input: nums = [1,4,3]
Output: 2
Explanation: [3,1,4] and [4,1,3] are the two special permutations of nums.

Constraints:

2 <= nums.length <= 14
1 <= nums[i] <= 10⁹

Approach overview

Problem Overview: You are given an array of distinct integers. The task is to count how many permutations exist such that for every adjacent pair (a, b), either a % b == 0 or b % a == 0. The result can be large, so it must be returned modulo 1e9 + 7.

Approach 1: Backtracking with Pruning (Time: O(n! * n), Space: O(n))

This approach generates permutations using classic backtracking. At each step, iterate through all unused elements and check if the current number forms a valid pair with the previously chosen number. If the divisibility condition fails, skip that branch immediately. This pruning significantly reduces the search space compared to generating all permutations. You maintain a visited structure to track which indices are already used and recursively build the permutation until its length reaches n.

The key insight is early rejection. Instead of building full permutations and validating afterward, the divisibility rule is checked while constructing the sequence. This approach is intuitive and useful for understanding the structure of the problem, but factorial growth still makes it expensive when n approaches the upper constraint.

Approach 2: Dynamic Programming with State Compression (Time: O(n^2 * 2^n), Space: O(n * 2^n))

The optimal solution uses dynamic programming combined with bitmask state compression. Represent the set of used indices with a bitmask of size n. Let dp[mask][last] store the number of valid permutations that use elements represented by mask and end at index last.

Transition by trying to append a new number. For every unused index next, check the divisibility condition with nums[last]. If valid, update dp[mask | (1 << next)][next]. The DP builds solutions incrementally from smaller subsets to larger ones. Because each state represents a unique combination of used elements, repeated computations from the backtracking approach disappear.

This method leverages the small constraint on n (typically ≤ 14). The total number of states is n * 2^n, and each transition checks up to n candidates. Precomputing which pairs satisfy the divisibility rule further speeds up transitions. The problem effectively becomes counting valid paths in a graph where edges exist between divisible numbers.

Recommended for interviews: Start by describing the backtracking idea to show you understand permutation generation and pruning. Then move to the optimized DP with bitmask solution. Interviewers typically expect the dynamic programming + bitmask approach because it reduces factorial complexity to O(n^2 * 2^n) while demonstrating mastery of subset DP on an array.

Approach 1: Backtracking with Pruning

This approach utilizes backtracking to explore all permutations. As we generate permutations, we backtrack whenever a permutation no longer satisfies the special condition. To improve efficiency, pruning is done whenever an invalid sequence is detected.

Python

MOD = 1000000007

def count_special_permutations(nums):
    def backtrack(pos, prev):
        if pos == len(nums):
            return 1

        total = 0
        for i in range(len(nums)):
            if not visited[i] and (prev == -1 or nums[i] % prev == 0 or prev % nums[i] == 0):
                visited[i] = True
                total = (total + backtrack(pos + 1, nums[i])) % MOD
                visited[i] = False
        return total

    visited = [False] * len(nums)
    return backtrack(0, -1)

# Example usage
nums = [2, 3, 6]
print(count_special_permutations(nums))

Java

import java.util.*;

public class SpecialPermutations {
    private static final int MOD = 1000000007;
    
    public static int countSpecialPermutations(int[] nums) {
        int n = nums.length;
        long[] result = {0};
        boolean[] visited = new boolean[n];
        
        backtrack(nums, n, visited, 0, -1, result);
        
        return (int) result[0];
    }
    
    private static void backtrack(int[] nums, int n, boolean[] visited, int pos, int prev, long[] result) {
        if (pos == n) {
            result[0] = (result[0] + 1) % MOD;
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!visited[i] && (prev == -1 || nums[i] % prev == 0 || prev % nums[i] == 0)) {
                visited[i] = true;
                backtrack(nums, n, visited, pos + 1, nums[i], result);
                visited[i] = false;
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {2, 3, 6};
        System.out.println(countSpecialPermutations(nums));
    }
}

C++

#include <iostream>
#include <vector>
using namespace std;
const int MOD = 1000000007;

int count_special_permutations(vector<int>& nums) {
    int n = nums.size();
    long result = 0;
    vector<int> visited(n, 0);

    function<void(int, int)> backtrack = [&](int pos, int prev) {
        if (pos == n) {
            result = (result + 1) % MOD;
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!visited[i] && (prev == -1 || nums[i] % prev == 0 || prev % nums[i] == 0)) {
                visited[i] = 1;
                backtrack(pos + 1, nums[i]);
                visited[i] = 0;
            }
        }
    };
    backtrack(0, -1);
    return result;
}

int main() {
    vector<int> nums = {2, 3, 6};
    cout << count_special_permutations(nums) << endl;
    return 0;
}

JavaScript

const MOD = 1000000007;

function countSpecialPermutations(nums) {
    const n = nums.length;
    let result = 0;
    const visited = new Array(n).fill(false);

    function backtrack(pos, prev) {
        if (pos === n) {
            result = (result + 1) % MOD;
            return;
        }
        for (let i = 0; i < n; i++) {
            if (!visited[i] && (prev === -1 || nums[i] % prev === 0 || prev % nums[i] === 0)) {
                visited[i] = true;
                backtrack(pos + 1, nums[i]);
                visited[i] = false;
            }
        }
    }

    backtrack(0, -1);
    return result;
}

// Example usage
const nums = [2, 3, 6];
console.log(countSpecialPermutations(nums));

#include <stdio.h>
#define MOD 1000000007

int count_special_permutations(int* nums, int numsSize) {
    long result = 0;
    int visited[numsSize];
    for (int i = 0; i < numsSize; i++) visited[i] = 0;

    void backtrack(int pos, int prev) {
        if (pos == numsSize) {
            result = (result + 1) % MOD;
            return;
        }
        for (int i = 0; i < numsSize; i++) {
            if (!visited[i] && (prev == -1 || nums[i] % prev == 0 || prev % nums[i] == 0)) {
                visited[i] = 1;
                backtrack(pos + 1, nums[i]);
                visited[i] = 0;
            }
        }
    }
    backtrack(0, -1);
    return result;
}

int main() {
    int nums[] = {2, 3, 6};
    int numsSize = 3;
    printf("%d\n", count_special_permutations(nums, numsSize));
    return 0;
}

using System;

class SpecialPermutations {
    const int MOD = 1000000007;
    
    public static int CountSpecialPermutations(int[] nums) {
        int n = nums.Length;
        long result = 0;
        bool[] visited = new bool[n];
        
        void Backtrack(int pos, int prev) {
            if (pos == n) {
                result = (result + 1) % MOD;
                return;
            }
            for (int i = 0; i < n; i++) {
                if (!visited[i] && (prev == -1 || nums[i] % prev == 0 || prev % nums[i] == 0)) {
                    visited[i] = true;
                    Backtrack(pos + 1, nums[i]);
                    visited[i] = false;
                }
            }
        }
        
        Backtrack(0, -1);
        return (int)result;
    }

    static void Main(string[] args) {
        int[] nums = { 2, 3, 6 };
        Console.WriteLine(CountSpecialPermutations(nums));
    }
}

This Python solution makes use of recursion (backtracking) to explore each possible permutation of the list, counting those that are special. It employs a visited list to avoid reusing elements.

Complexity

Time Complexity: O(n!) due to generating permutations.
Space Complexity: O(n) for the recursion stack and visited list.

Try this approach in the editor

Approach 2: Dynamic Programming with State Compression

This approach leverages dynamic programming to efficiently count special permutations by remembering the states of partial permutations using bitmasks. The DP table is used to store solutions to subproblems, avoiding repeated calculations.

Python

MOD = 1000000007


def count_special_permutations(nums):
    n = len(nums)
    dp = [[-1] * n for _ in range(1 << n)]

    def dfs(mask, last):
        if mask == (1 << n) - 1:
            return 1
        if dp[mask][last] != -1:
            return dp[mask][last]

        result = 0
        for i in range(n):
            if not (mask & (1 << i)) and (nums[last] % nums[i] == 0 or nums[i] % nums[last] == 0):
                result = (result + dfs(mask | (1 << i), i)) % MOD
        dp[mask][last] = result
        return result

    total = 0
    for i in range(n):
        total = (total + dfs(1 << i, i)) % MOD

    return total


# Example usage
nums = [2, 3, 6]
print(count_special_permutations(nums))

Java

public class SpecialPermutations {
    private static final int MOD = 1000000007;
    private static long[][] dp;

    public static int countSpecialPermutations(int[] nums) {
        int n = nums.length;
        dp = new long[1 << n][n];
        for (long[] row : dp) Arrays.fill(row, -1);
        long total = 0;
        for (int i = 0; i < n; i++) {
            total = (total + dfs(nums, (1 << i), i)) % MOD;
        }
        return (int)total;
    }

    private static long dfs(int[] nums, int mask, int last) {
        if (mask == (1 << nums.length) - 1) return 1;
        if (dp[mask][last] != -1) return dp[mask][last];

        long result = 0;
        for (int i = 0; i < nums.length; i++) {
            if ((mask & (1 << i)) == 0 && (nums[last] % nums[i] == 0 || nums[i] % nums[last] == 0)) {
                result = (result + dfs(nums, mask | (1 << i), i)) % MOD;
            }
        }
        return dp[mask][last] = result;
    }

    public static void main(String[] args) {
        int[] nums = {2, 3, 6};
        System.out.println(countSpecialPermutations(nums));
    }
}

C++

#include <iostream>
#include <vector>
using namespace std;
const int MOD = 1000000007;

vector<vector<int>> dp;

int dfs(vector<int>& nums, int mask, int last) {
    if (mask == (1 << nums.size()) - 1) return 1;
    if (dp[mask][last] != -1) return dp[mask][last];

    int result = 0;
    for (int i = 0; i < nums.size(); i++) {
        if (!(mask & (1 << i)) && (last == -1 || nums[last] % nums[i] == 0 || nums[i] % nums[last] == 0)) {
            result = (result + dfs(nums, mask | (1 << i), i)) % MOD;
        }
    }
    return dp[mask][last] = result;
}

int count_special_permutations(vector<int>& nums) {
    int n = nums.size();
    dp = vector<vector<int>>(1 << n, vector<int>(n, -1));
    int total = 0;
    for (int i = 0; i < n; i++) {
        total = (total + dfs(nums, 1 << i, i)) % MOD;
    }
    return total;
}

int main() {
    vector<int> nums = {2, 3, 6};
    cout << count_special_permutations(nums) << endl;
    return 0;
}

JavaScript

const MOD = 1000000007;

function countSpecialPermutations(nums) {
    const n = nums.length;
    const dp = Array.from({ length: 1 << n }, () => Array(n).fill(-1));

    function dfs(mask, last) {
        if (mask === (1 << n) - 1) return 1;
        if (dp[mask][last] !== -1) return dp[mask][last];

        let result = 0;
        for (let i = 0; i < n; i++) {
            if (!(mask & (1 << i)) && (nums[last] % nums[i] === 0 || nums[i] % nums[last] === 0)) {
                result = (result + dfs(mask | (1 << i), i)) % MOD;
            }
        }
        return dp[mask][last] = result;
    }

    let total = 0;
    for (let i = 0; i < n; i++) {
        total = (total + dfs(1 << i, i)) % MOD;
    }
    return total;
}

// Example usage
const nums = [2, 3, 6];
console.log(countSpecialPermutations(nums));

#include <stdio.h>
#include <string.h>
#define MOD 1000000007

long dp[1<<14][14];

int count_special_permutations(int* nums, int numsSize) {
    memset(dp, -1, sizeof(dp));

    long dfs(int mask, int last) {
        if (mask == (1 << numsSize) - 1) return 1;
        if (dp[mask][last] != -1) return dp[mask][last];

        long result = 0;
        for (int i = 0; i < numsSize; i++) {
            if (!(mask & (1 << i)) && (last == -1 || nums[last] % nums[i] == 0 || nums[i] % nums[last] == 0)) {
                result = (result + dfs(mask | (1 << i), i)) % MOD;
            }
        }
        return dp[mask][last] = result;
    }

    long total = 0;
    for (int i = 0; i < numsSize; i++) {
        total = (total + dfs(1 << i, i)) % MOD;
    }
    return total;
}

int main() {
    int nums[] = {2, 3, 6};
    printf("%d\n", count_special_permutations(nums, 3));
    return 0;
}

using System;

class SpecialPermutations {
    const int MOD = 1000000007;
    static long[,] dp;

    public static int CountSpecialPermutations(int[] nums) {
        int n = nums.Length;
        dp = new long[1 << n, n];
        for (int i = 0; i < (1 << n); i++)
            for (int j = 0; j < n; j++)
                dp[i, j] = -1;

        long total = 0;
        for (int i = 0; i < n; i++) {
            total = (total + Dfs(nums, (1 << i), i)) % MOD;
        }
        return (int)total;
    }

    static long Dfs(int[] nums, int mask, int last) {
        if (mask == (1 << nums.Length) - 1) return 1;
        if (dp[mask, last] != -1) return dp[mask, last];

        long result = 0;
        for (int i = 0; i < nums.Length; i++) {
            if ((mask & (1 << i)) == 0 && (nums[last] % nums[i] == 0 || nums[i] % nums[last] == 0)) {
                result = (result + Dfs(nums, mask | (1 << i), i)) % MOD;
            }
        }
        dp[mask, last] = result;
        return result;
    }

    static void Main(string[] args) {
        int[] nums = { 2, 3, 6 };
        Console.WriteLine(CountSpecialPermutations(nums));
    }
}

Python implementation uses DP with state compression. The function \dfs\> leverages memoized states to compute valid permutations efficiently and reduce redundant calculation.

Complexity

Time Complexity: O(n^2 * 2^n), due to state exploration.
Space Complexity: O(n * 2^n) for DP arrays.

Try this approach in the editor

Approach 3: State Compression Dynamic Programming

We notice that the maximum length of the array in the problem does not exceed 14. Therefore, we can use an integer to represent the current state, where the i-th bit is 1 if the i-th number in the array has been selected, and 0 if it has not been selected.

We define f[i][j] as the number of schemes where the current selected integer state is i, and the index of the last selected integer is j. Initially, f[0][0]=0, and the answer is sum_{j=0}^{n-1}f[2^n-1][j].

Considering f[i][j], if only one number is currently selected, then f[i][j]=1. Otherwise, we can enumerate the index k of the last selected number. If the numbers corresponding to k and j meet the requirements of the problem, then f[i][j] can be transferred from f[i \oplus 2^j][k]. That is:

$f[i][j]= \begin{cases} 1, & i=2^j\ sum_{k=0}^{n-1}f[i \oplus 2^j][k], & i neq 2^j and nums[j] and nums[k] meet the requirements of the problem\ \end{cases}

The final answer is sum_{j=0}^{n-1}f[2^n-1][j]. Note that the answer may be very large, so we need to take the modulus of 10^9+7.

The time complexity is O(n^2 times 2^n), and the space complexity is O(n times 2^n). Here, n$ is the length of the array.

TypeScript

function specialPerm(nums: number[]): number {
    const mod = 1e9 + 7;
    const n = nums.length;
    const m = 1 << n;
    const f = Array.from({ length: m }, () => Array(n).fill(0));

    for (let i = 1; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            if (((i >> j) & 1) === 1) {
                const ii = i ^ (1 << j);
                if (ii === 0) {
                    f[i][j] = 1;
                    continue;
                }
                for (let k = 0; k < n; ++k) {
                    if (nums[j] % nums[k] === 0 || nums[k] % nums[j] === 0) {
                        f[i][j] = (f[i][j] + f[ii][k]) % mod;
                    }
                }
            }
        }
    }

    return f[m - 1].reduce((acc, x) => (acc + x) % mod);
}

func specialPerm(nums []int) (ans int) {
	const mod int = 1e9 + 7
	n := len(nums)
	m := 1 << n
	f := make([][]int, m)
	for i := range f {
		f[i] = make([]int, n)
	}
	for i := 1; i < m; i++ {
		for j, x := range nums {
			if i>>j&1 == 1 {
				ii := i ^ (1 << j)
				if ii == 0 {
					f[i][j] = 1
					continue
				}
				for k, y := range nums {
					if x%y == 0 || y%x == 0 {
						f[i][j] = (f[i][j] + f[ii][k]) % mod
					}
				}
			}
		}
	}
	for _, x := range f[m-1] {
		ans = (ans + x) % mod
	}
	return
}

Rust

impl Solution {
    pub fn special_perm(nums: Vec<i32>) -> i32 {
        const MOD: i32 = 1_000_000_007;
        let n = nums.len();
        let m = 1 << n;
        let mut f = vec![vec![0; n]; m];

        for i in 1..m {
            for j in 0..n {
                if (i >> j) & 1 == 1 {
                    let ii = i ^ (1 << j);
                    if ii == 0 {
                        f[i][j] = 1;
                        continue;
                    }
                    for k in 0..n {
                        if nums[j] % nums[k] == 0 || nums[k] % nums[j] == 0 {
                            f[i][j] = (f[i][j] + f[ii][k]) % MOD;
                        }
                    }
                }
            }
        }

        let mut ans = 0;
        for &x in &f[m - 1] {
            ans = (ans + x) % MOD;
        }

        ans
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Backtracking with Pruning	Time Complexity: O(n!) due to generating permutations. Space Complexity: O(n) for the recursion stack and visited list.
Dynamic Programming with State Compression	Time Complexity: O(n^2 * 2^n), due to state exploration. Space Complexity: O(n * 2^n) for DP arrays.
State Compression Dynamic Programming	–

Complexity analysis

Approach	Time	Space	When to Use
Backtracking with Pruning	O(n! * n)	O(n)	Good for understanding permutation generation and constraint pruning. Works for small n but becomes slow near upper limits.
DP with State Compression (Bitmask)	O(n^2 * 2^n)	O(n * 2^n)	Best general solution for n ≤ 14. Avoids recomputation by caching subset states.

Frequently asked questions

Is Special Permutations easy or hard?

Special Permutations is generally considered a medium-to-hard dynamic programming problem. The challenge comes from recognizing that brute-force permutations are too slow and switching to subset DP with bitmask optimization.

How to solve Special Permutations in O(n^2 * 2^n)?

Use dynamic programming with a bitmask representing which indices are used. Maintain dp[mask][last] as the count of permutations ending at index 'last'. Transition by adding unused elements that satisfy the divisibility condition with the last element.

What is the best approach for Special Permutations?

Dynamic programming with bitmask state compression is the most efficient approach. It tracks which elements are already used with a bitmask and stores results in dp[mask][last]. This reduces the complexity to O(n^2 * 2^n), which works well for n up to about 14.

Is Special Permutations asked at Google/Amazon/Meta?

The problem style appears frequently in interviews at large tech companies because it combines permutation generation with dynamic programming and bitmask optimization. Similar subset DP problems are common at companies like Google, Amazon, and Meta.

What data structure is used in Special Permutations?

The core data structure is a DP table indexed by bitmask and the last chosen index. Bitmasks efficiently represent subsets of the array, while the DP table stores counts of valid permutations for each state.

What is the time complexity of Special Permutations?

The optimal DP with state compression runs in O(n^2 * 2^n) time and uses O(n * 2^n) space. A naive permutation approach with backtracking can reach O(n! * n) time because it explores nearly all permutations in the worst case.

Special Permutations Python or Java solution approach?

Both Python and Java implementations typically use the same DP with bitmask strategy. The solution maintains a 2D DP array or memoized recursion where states are defined by the used-element mask and the last selected index.

Special Permutations solution and explanation

The problem

Approach overview

Approach 1: Backtracking with Pruning

Approach 2: Dynamic Programming with State Compression

Approach 3: State Compression Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Special Permutations solution and explanation

The problem

Approach overview

Approach 1: Backtracking with Pruning

Approach 2: Dynamic Programming with State Compression

Approach 3: State Compression Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems