Description
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 109 + 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 <= 141 <= nums[i] <= 109
Solutions
Solution 1: 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 ∑_{j=0}n-1f[2n-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 2j][k]. That is:
f[i][j]=
\begin{cases}
1, & i=2j\
∑_{k=0}n-1f[i \oplus 2j][k], & i ≠ 2j and nums[j] and nums[k] meet the requirements of the problem\
\end{cases}
The final answer is ∑_{j=0}n-1f[2n-1][j]. Note that the answer may be very large, so we need to take the modulus of 109+7.
The time complexity is O(n2 × 2n), and the space complexity is O(n × 2n). Here, n is the length of the array.
PythonJavaC++GoTypeScriptRust
class Solution:
def specialPerm(self, nums: List[int]) -> int:
mod = 10**9 + 7
n = len(nums)
m = 1 << n
f = [[0] * n for _ in range(m)]
for i in range(1, m):
for j, x in enumerate(nums):
if i >> j & 1:
ii = i ^ (1 << j)
if ii == 0:
f[i][j] = 1
continue
for k, y in enumerate(nums):
if x % y == 0 or y % x == 0:
f[i][j] = (f[i][j] + f[ii][k]) % mod
return sum(f[-1]) % mod(code-box)
class Solution {
public int specialPerm(int[] nums) {
final int mod = (int) 1e9 + 7;
int n = nums.length;
int m = 1 << n;
int[][] f = new int[m][n];
for (int i = 1; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if ((i >> j & 1) == 1) {
int ii = i ^ (1 << j);
if (ii == 0) {
f[i][j] = 1;
continue;
}
for (int 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;
}
}
}
}
}
int ans = 0;
for (int x : f[m - 1]) {
ans = (ans + x) % mod;
}
return ans;
}
}(code-box)
class Solution {
public:
int specialPerm(vector<int>& nums) {
const int mod = 1e9 + 7;
int n = nums.size();
int m = 1 << n;
int f[m][n];
memset(f, 0, sizeof(f));
for (int i = 1; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if ((i >> j & 1) == 1) {
int ii = i ^ (1 << j);
if (ii == 0) {
f[i][j] = 1;
continue;
}
for (int 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;
}
}
}
}
}
int ans = 0;
for (int x : f[m - 1]) {
ans = (ans + x) % mod;
}
return ans;
}
};(code-box)
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
}(code-box)
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);
}(code-box)
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
}
}(code-box)
