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 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

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

Practice these live with InterviewChamp.AI

Drill Beautiful Arrangement and Recursion problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →