Beautiful Arrangement

Beautiful Arrangement

What is this problem about?

The "Beautiful Arrangement interview question" is a permutation problem with a twist. Given an integer $n$, you need to construct a permutation of numbers from $1$ to $n$. A permutation is "beautiful" if for every position $i$ ($1$-indexed), either the number at that position is divisible by $i$, or $i$ is divisible by the number. Your goal is to find the total count of such beautiful arrangements.

Why is this asked in interviews?

Salesforce and Google use the "Beautiful Arrangement coding problem" to evaluate a candidate's mastery of Backtracking. It’s a classic search problem where the state space is large ($n!$), but many branches can be "pruned" early because they violate the divisibility rule. It also opens the door for optimizations like bitmasking and memoization.

Algorithmic pattern used

The core pattern is Backtracking with Pruning.

1. Recursive Function: Define a function solve(pos) that tries to place a number in the current position pos.
2. Loop and Validate: Iterate through all numbers from $1$ to $n$.
3. Pruning: If the number is not yet used AND (number % pos == 0 OR pos % number == 0), then place the number and move to solve(pos + 1).
4. Base Case: If pos > n, you've successfully built a beautiful arrangement. Increment the counter.
5. Memoization (Optional): Use a bitmask to represent the set of used numbers and store the result for each (pos, mask) pair to avoid re-computing.

Example explanation

$n = 2$. Possible numbers: {1, 2}.

• Position 1:
  • Can we put 1? Yes (1 is divisible by 1).
    • Position 2: Remaining {2}. Can we put 2? Yes (2 is divisible by 2). Arrangement 1: [1, 2].
  • Can we put 2? Yes (2 is divisible by 1).
    • Position 2: Remaining {1}. Can we put 1? Yes (2 is divisible by 1). Arrangement 2: [2, 1]. Total: 2.

Common mistakes candidates make

• Inefficient Validation: Generating all permutations first and then checking them ($O(n imes n!)$). Pruning must happen during generation.
• State Pollution: Forgetting to mark a number as "unused" (backtracking step) after the recursive call returns.
• 1-indexing confusion: Mixing up 0-based array indexing with the 1-based logic of the problem.

Interview preparation tip

Backtracking is essentially DFS on a state space tree. Practice visualizing the tree and identifying where you can cut off branches. This "Backtracking interview pattern" is fundamental for solving constraint-satisfaction problems.