Skip to main content

526. Beautiful Arrangement

medium

Count permutations of 1..n where for every position i (1-indexed), either i divides arr[i] or arr[i] divides i. Classic backtracking with a divisibility constraint plus a clean bitmask optimization.

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

Place numbers one position at a time. At position p (1..n), try every unused number k for which p % k == 0 or k % p == 0.

Hint 2

Track used numbers — a boolean array or, better, a bitmask.

Hint 3

Memoize on (position, usedMask). Two states with the same mask yield the same suffix count.

Hint 4

Iterating position from n down to 1 lets you prune harder positions first.

Solution approach

Reveal approach

Backtracking with a boolean used[] array — or bitmask for speed. count(position): if position > n, increment count and return. For k from 1 to n: if !used[k] and (k % position == 0 or position % k == 0), set used[k] = true, recurse(position + 1), set used[k] = false. Starting from position 1 works. The bitmask version uses an integer mask of n bits; memoize on (position, mask) — same state always produces the same suffix count. Time is O(n!) worst case, but the divisibility constraint prunes most branches; the bitmask + memo cuts to O(n * 2^n). Space O(n) or O(2^n) for the memo.

Complexity

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

Related patterns

  • backtracking
  • recursion
  • bitmask-dp
  • permutations

Related problems

Asked at

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

  • Amazon

More Recursion practice problems

See all Recursion problems →