Beautiful Arrangement
Medium Bitmask DP
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Count permutations of 1..n (n ≤ 15) where, at every position i (1-indexed), either the number divides i or i divides the number.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: count arrangements where every position and its number divide one way or the other.
Why this works: the set of numbers already used is a bitmask, and the next position is its popcount + 1. dp[mask] counts the ways.
Example: n = 2
[1, 2] ✓, [2, 1] ✓ → 2✦Hints open one at a time
↗Approach
dp[mask] = ways to fill the first popcount(mask) positions using exactly the numbers in mask. For each mask, let pos = bitCount(mask) + 1 and try every unused number that fits pos.
</>Solution (Java)
class Solution {
public int countArrangement(int n) {
int[] dp = new int[1 << n];
dp[0] = 1;
for (int mask = 0; mask < (1 << n); mask++) {
if (dp[mask] == 0) continue;
int pos = Integer.bitCount(mask) + 1; // next position to fill
for (int num = 1; num <= n; num++) {
int bit = 1 << (num - 1);
if ((mask & bit) == 0 && (num % pos == 0 || pos % num == 0)) {
dp[mask | bit] += dp[mask];
}
}
}
return dp[(1 << n) - 1];
}
}!Common mistake
Storing the position as part of the state — it's determined by the mask already.
- Time: O(2^n · n).
- Space: O(2^n).