526. Beautiful Arrangement
mediumCount 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 Alex Chen, 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
n = 22Explanation: 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
n = 11Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
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).
Practice these live with InterviewChamp.AI
Drill Beautiful Arrangement and Bit Manipulation problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →