Problem statement

Take a permutation perm of the integers 1 to n, indexed from 1. It is a beautiful arrangement if, for every position i (1 <= i <= n), either perm[i] is divisible by i or i is divisible by perm[i].

Given n, return the number of beautiful arrangements.

Example 1

Input: n = 3
Output: 3
Explanation: `[1,2,3]`, `[2,1,3]` and `[3,2,1]`. In `[1,3,2]`, position 2 holds 3, and neither divides the other.

Example 2

Input: n = 4
Output: 8

Example 3

Input: n = 6
Output: 36

Constraints

• 1 <= n <= 15

Hints for Beautiful Arrangement

1. Hint 1

   Fill the positions one at a time and only place a number that is compatible with its position — most branches die early.

2. Hint 2

   The only thing that matters for the remaining positions is which numbers are already used: a 15-bit mask.

3. Hint 3

   Let dp[mask] count the ways to fill positions 1..popcount(mask) with exactly the numbers in mask; extend it by placing each compatible unused number at position popcount(mask) + 1.

How to solve Beautiful Arrangement

Positions are filled in order, so the next position is determined by how many numbers are used; the state is just the set of used numbers, and a DP over the 2^n subsets counts all valid permutations.

Approach

1. Set dp[0] = 1.
2. For each mask with dp[mask] > 0, let pos = popcount(mask) + 1.
3. For each number v not in mask with v % pos == 0 or pos % v == 0, add dp[mask] to dp[mask | bit(v)].
4. Return dp[2^n - 1].

Why it works

Every beautiful arrangement corresponds to exactly one sequence of placements (position 1, then 2, …), and each prefix of that sequence is a used-set mask whose count includes it. Whether the rest can be completed depends only on the used set, so merging all prefixes with the same mask counts each arrangement exactly once.

Complexity

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

Pitfalls

• Positions are 1-indexed; with 0-indexing the divisibility test breaks (everything divides 0).
• Either direction of divisibility is enough.
• Generating all n! permutations and filtering is far too slow for n = 15.

Reference solution

Python

def countArrangement(n: int) -> int:
    full = 1 << n
    dp = [0] * full
    dp[0] = 1
    for mask in range(full):
        ways = dp[mask]
        if not ways:
            continue
        pos = bin(mask).count("1") + 1
        for v in range(1, n + 1):
            bit = 1 << (v - 1)
            if mask & bit:
                continue
            if v % pos == 0 or pos % v == 0:
                dp[mask | bit] += ways
    return dp[full - 1]

Java

public static int countArrangement(int n) {
    int full = 1 << n;
    int[] dp = new int[full];
    dp[0] = 1;
    for (int mask = 0; mask < full; mask++) {
        if (dp[mask] == 0) continue;
        int pos = Integer.bitCount(mask) + 1;
        for (int v = 1; v <= n; v++) {
            int bit = 1 << (v - 1);
            if ((mask & bit) != 0) continue;
            if (v % pos == 0 || pos % v == 0) dp[mask | bit] += dp[mask];
        }
    }
    return dp[full - 1];
}

C++

int countArrangement(int n) {
    int full = 1 << n;
    vector<int> dp(full, 0);
    dp[0] = 1;
    for (int mask = 0; mask < full; mask++) {
        if (!dp[mask]) continue;
        int pos = __builtin_popcount(mask) + 1;
        for (int v = 1; v <= n; v++) {
            int bit = 1 << (v - 1);
            if (mask & bit) continue;
            if (v % pos == 0 || pos % v == 0) dp[mask | bit] += dp[mask];
        }
    }
    return dp[full - 1];
}

JavaScript

var countArrangement = function(n) {
    var full = 1 << n, dp = new Array(full).fill(0);
    dp[0] = 1;
    for (var mask = 0; mask < full; mask++) {
        if (!dp[mask]) continue;
        var pos = 1;
        for (var x = mask; x; x >>= 1) pos += x & 1;
        for (var v = 1; v <= n; v++) {
            var bit = 1 << (v - 1);
            if (mask & bit) continue;
            if (v % pos === 0 || pos % v === 0) dp[mask | bit] += dp[mask];
        }
    }
    return dp[full - 1];
};

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

More dynamic programming problems

• Largest BST in a Binary Tree Medium
• Longest ZigZag Path in a Binary Tree Medium
• House Robber III Medium
• Find Good Days to Rob the Bank Medium
• Minimum Increments to Equalize Leaf Paths Medium
• Disconnect Path in a Binary Matrix by at Most One Flip Medium