2848. Special Permutations¶

Difficulty: Medium

2848. Special Permutations

Medium

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⁹

Solution¶

import java.util.ArrayList;
import java.util.Arrays;

class Solution {
    private int dp[][];
    private int mod = (int)(1e9 + 7);

    public int specialPerm(int[] nums) {
        int n = nums.length;
        dp = new int[n + 1][(1 << n) + 1];
        for (int current[] : dp)
            Arrays.fill(current, -1);

        return solve(0, -1, nums, new ArrayList<>());
    }

    private int solve(int ind, int prev, int arr[], ArrayList<Integer> selected) {
        if (selected.size() == arr.length)
            return 1;

        int mask = 0;
        for (int ele : selected)
            mask |= (1 << ele);

        if (dp[prev + 1][mask] != -1)
            return dp[prev + 1][mask];

        int res = 0;
        for (int i = 0; i < arr.length; i++) {
            if (!selected.contains(i)) {
                if (prev == -1 || arr[i] % arr[prev] == 0 || arr[prev] % arr[i] == 0) {
                    selected.add(i);
                    res = (res + solve(ind + 1, i, arr, selected)) % mod;
                    selected.remove(selected.size() - 1);
                }
            }
        }
        return dp[prev + 1][mask] = res;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here