Skip to main content

526. Beautiful Arrangement

medium

Count permutations of 1..n where every position i satisfies arr[i] % i == 0 or i % arr[i] == 0. Classic bitmask DP — backtracking with memoization on the used-set.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Suppose you have n integers labeled 1 through n. A permutation of those n integers perm (1-indexed) is considered a beautiful arrangement if for every i (1 <= i <= n), either of the following is true: perm[i] is divisible by i, or i is divisible by perm[i]. Given an integer n, return the number of the beautiful arrangements that you can construct.

Constraints

  • 1 <= n <= 15

Examples

Example 1

Input
n = 2
Output
2

Explanation: The first beautiful arrangement is [1,2]: perm[1] = 1 is divisible by i = 1; perm[2] = 2 is divisible by i = 2. The second beautiful arrangement is [2,1]: perm[1] = 2 is divisible by i = 1; i = 2 is divisible by perm[2] = 1.

Example 2

Input
n = 1
Output
1

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

n! grows fast — at n = 15 it's about 1.3 * 10^12. Pure permutation enumeration is hopeless.

Hint 2

But there are only 2^n possible 'used number' bitmasks — 32768 for n = 15. State-space DP saves you.

Hint 3

DP state: dp[mask] = number of beautiful prefixes that use exactly the numbers in mask. The prefix length equals popcount(mask).

Hint 4

Transition: dp[mask] = sum over each bit k set in mask of dp[mask ^ (1 << k)] if (k+1) is divisible by popcount(mask) or vice versa.

Solution approach

Reveal approach

Bitmask DP on the set of used numbers. Let pos = popcount(mask) be the position being filled. dp[0] = 1 (empty arrangement). For each non-empty mask, dp[mask] = Σ over each set bit k in mask of dp[mask ^ (1 << k)] when number (k + 1) is placeable at position pos — that is, (k + 1) % pos == 0 or pos % (k + 1) == 0. The answer is dp[(1 << n) - 1]. There are 2^n masks and each scan costs O(n), so total time is O(n * 2^n) = ~500k operations for n = 15. Space O(2^n). The recursion-with-memoization variant is equally clean and often easier to write under pressure.

Complexity

Time
O(n * 2^n)
Space
O(2^n)

Related patterns

  • bit-manipulation
  • dynamic-programming
  • bitmask-dp
  • backtracking

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Google

More Bit Manipulation practice problems

See all Bit Manipulation problems →