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.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming, Bit Manipulation, Bitmask
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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 <= 141 <= nums[i] <= 10^9All values in nums are distinct
Hints for Special Permutations
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?
Hint 2
Only the set of used elements and the last element matter.
Hint 3
Let
dp[mask][last]count the orderings of the elements inmaskthat end withlast; extend with any unusedjthat divides or is divided bynums[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
- Precompute
ok[i][j]=nums[i] % nums[j] == 0 || nums[j] % nums[i] == 0. - Set
dp[1 << i][i] = 1for everyi. - For each
maskin increasing order and eachlastwithdp[mask][last] > 0, add it todp[mask | 1<<j][j]for everyjnot inmaskwithok[last][j], modulo10^9 + 7. - Return the sum of
dp[2^n - 1][last]over alllast.
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]) % modJava
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