Special Permutations

Medium
1345.

Special Permutations

Special Permutations is a medium coding problem on arrays, dynamic programming and bit manipulation, asked in Amazon and Google interviews.

You are given an array nums of n distinct positive integers. A permutation of nums is special if every pair of neighbours divides one way or the other: for all 0 <= i < n - 1, either nums[i] % nums[i+1] == 0 or nums[i+1] % nums[i] == 0.

Return the number of special permutations modulo 10^9 + 7.

Example 1

Input
nums = [4,2,8]
Output
6
Explanation
Every pair divides, so all 3! orders are special.

Example 2

Input
nums = [3,5]
Output
0

Example 3

Input
nums = [1,6,3,5]
Output
4
Explanation
5 only pairs with 1, so it sits at an end next to 1: [5,1,6,3], [5,1,3,6] and their reverses.

Constraints

  • 2 <= nums.length <= 14
  • 1 <= nums[i] <= 10^9
  • All values in nums are distinct
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var specialPerm = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Special Permutations — Solution in Python, Java & C++

Special Permutations solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Special Permutations is a medium coding problem on arrays, dynamic programming and bit manipulation, asked in Amazon and Google interviews.

Problem statement

You are given an array nums of n distinct positive integers. A permutation of nums is special if every pair of neighbours divides one way or the other: for all 0 <= i < n - 1, either nums[i] % nums[i+1] == 0 or nums[i+1] % nums[i] == 0.

Return the number of special permutations modulo 10^9 + 7.

Example 1

Input: nums = [4,2,8]
Output: 6
Explanation: Every pair divides, so all 3! orders are special.

Example 2

Input: nums = [3,5]
Output: 0

Example 3

Input: nums = [1,6,3,5]
Output: 4
Explanation: 5 only pairs with 1, so it sits at an end next to 1: [5,1,6,3], [5,1,3,6] and their reverses.

Constraints

  • 2 <= nums.length <= 14
  • 1 <= nums[i] <= 10^9
  • All values in nums are distinct

Hints for Special Permutations

  1. Hint 1

    Build the permutation left to right. What do you need to know about the part already built to decide what may come next?

  2. Hint 2

    Only the set of used elements and the last element matter.

  3. Hint 3

    Let dp[mask][last] count the orderings of the elements in mask that end with last; extend with any unused j that divides or is divided by nums[last].

How to solve Special Permutations

A special permutation is a Hamiltonian path in the "divides" graph; counting them is the classic bitmask DP over (used set, last element).

Approach

  1. Precompute ok[i][j] = nums[i] % nums[j] == 0 || nums[j] % nums[i] == 0.
  2. Set dp[1 << i][i] = 1 for every i.
  3. For each mask in increasing order and each last with dp[mask][last] > 0, add it to dp[mask | 1<<j][j] for every j not in mask with ok[last][j], modulo 10^9 + 7.
  4. Return the sum of dp[2^n - 1][last] over all last.

Why it works

The validity of the next element depends only on the previous one, and the elements still available depend only on the used set, so (mask, last) captures everything needed to continue. Each special permutation is counted along its unique sequence of prefixes, ending in the full mask with its own last element.

Complexity

  • Time — O(n² · 2^n)
  • Space — O(n · 2^n)

Pitfalls

  • Check divisibility in both directions.
  • Start every element as a possible first element — dp[1<<i][i] = 1, not only index 0.
  • Take the modulus while adding; with 14 elements the counts can exceed 32 bits.

Reference solution

Python

from typing import List

def specialPerm(nums: List[int]) -> int:
    mod = 1000000007
    n = len(nums)
    full = 1 << n
    ok = [[i != j and (nums[i] % nums[j] == 0 or nums[j] % nums[i] == 0) for j in range(n)] for i in range(n)]
    dp = [[0] * n for _ in range(full)]
    for i in range(n):
        dp[1 << i][i] = 1
    for mask in range(1, full):
        row = dp[mask]
        for last in range(n):
            w = row[last]
            if not w:
                continue
            for j in range(n):
                if (mask >> j) & 1 or not ok[last][j]:
                    continue
                nm = mask | (1 << j)
                dp[nm][j] = (dp[nm][j] + w) % mod
    return sum(dp[full - 1]) % mod

Java

public static int specialPerm(int[] nums) {
    final int M = 1000000007;
    int n = nums.length, full = 1 << n;
    boolean[][] ok = new boolean[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) ok[i][j] = i != j && (nums[i] % nums[j] == 0 || nums[j] % nums[i] == 0);
    }
    int[][] dp = new int[full][n];
    for (int i = 0; i < n; i++) dp[1 << i][i] = 1;
    for (int mask = 1; mask < full; mask++) {
        for (int last = 0; last < n; last++) {
            int w = dp[mask][last];
            if (w == 0) continue;
            for (int j = 0; j < n; j++) {
                if (((mask >> j) & 1) == 1 || !ok[last][j]) continue;
                int nm = mask | (1 << j);
                dp[nm][j] = (dp[nm][j] + w) % M;
            }
        }
    }
    int total = 0;
    for (int e = 0; e < n; e++) total = (total + dp[full - 1][e]) % M;
    return total;
}

C++

int specialPerm(vector<int>& nums) {
    const int M = 1000000007;
    int n = nums.size(), full = 1 << n;
    vector<vector<bool>> ok(n, vector<bool>(n, false));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) ok[i][j] = i != j && (nums[i] % nums[j] == 0 || nums[j] % nums[i] == 0);
    }
    vector<vector<int>> dp(full, vector<int>(n, 0));
    for (int i = 0; i < n; i++) dp[1 << i][i] = 1;
    for (int mask = 1; mask < full; mask++) {
        for (int last = 0; last < n; last++) {
            int w = dp[mask][last];
            if (!w) continue;
            for (int j = 0; j < n; j++) {
                if (((mask >> j) & 1) || !ok[last][j]) continue;
                int nm = mask | (1 << j);
                dp[nm][j] = (dp[nm][j] + w) % M;
            }
        }
    }
    int total = 0;
    for (int e = 0; e < n; e++) total = (total + dp[full - 1][e]) % M;
    return total;
}

JavaScript

var specialPerm = function(nums) {
    var M = 1000000007, n = nums.length, full = 1 << n;
    var ok = [];
    for (var i = 0; i < n; i++) {
        ok.push([]);
        for (var j = 0; j < n; j++) ok[i].push(i !== j && (nums[i] % nums[j] === 0 || nums[j] % nums[i] === 0));
    }
    var dp = new Array(full * n).fill(0);
    for (var s = 0; s < n; s++) dp[(1 << s) * n + s] = 1;
    for (var mask = 1; mask < full; mask++) {
        for (var last = 0; last < n; last++) {
            var w = dp[mask * n + last];
            if (!w) continue;
            for (var nx = 0; nx < n; nx++) {
                if (((mask >> nx) & 1) || !ok[last][nx]) continue;
                var at = (mask | (1 << nx)) * n + nx;
                dp[at] = (dp[at] + w) % M;
            }
        }
    }
    var total = 0;
    for (var e = 0; e < n; e++) total = (total + dp[(full - 1) * n + e]) % M;
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming