Welcome to Subscribe On Youtube

2741. Special Permutations

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 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] <= 109

Solutions

  • 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;
        }
    }
    
  • 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;
        }
    };
    
  • 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
    
    
  • 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
    }
    
  • 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);
    }
    
    
  • 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
        }
    }
    
    

All Problems

All Solutions