LeetCode 526 - Beautiful Arrangement

The problem asks us to count how many permutations of the integers from 1 to n satisfy a special divisibility condition. A permutation is an arrangement of all numbers from 1 to n where every number appears exactly once.

leetcodemediumarraydynamic-programmingbacktrackingbit-manipulationbitmask

LeetCode Problem 526

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Backtracking, Bit Manipulation, Bitmask

Solution

Problem Understanding

The problem asks us to count how many permutations of the integers from 1 to n satisfy a special divisibility condition.

A permutation is an arrangement of all numbers from 1 to n where every number appears exactly once. For example, when n = 3, the possible permutations include [1,2,3], [2,1,3], [3,2,1], and so on.

A permutation is considered a beautiful arrangement if, for every position i using 1-based indexing, at least one of the following conditions holds:

  • perm[i] % i == 0
  • i % perm[i] == 0

In other words, the number placed at position i must either divide the index evenly or be divisible by the index evenly.

The input is a single integer n, and the output is the total number of valid beautiful arrangements.

The constraint 1 <= n <= 15 is extremely important. A naive solution that generates all permutations would require checking up to:

$$15! = 1,307,674,368,000$$

possible arrangements, which is far too large for brute force enumeration.

This constraint strongly suggests that we need a more intelligent search strategy, typically involving:

  • Backtracking
  • Dynamic programming
  • Bitmasking
  • State pruning

The small upper bound of 15 also hints that bitmask dynamic programming is practical because a bitmask of length 15 fits comfortably inside an integer.

Several edge cases are important:

  • n = 1 is the smallest possible input, and the only arrangement is trivially valid.
  • Some positions have very few valid numbers, so choosing values inefficiently can create unnecessary branching.
  • Since each number can only be used once, we must carefully track usage state during recursion.
  • Duplicate counting must be avoided, meaning every valid permutation should be counted exactly once.

Approaches

Brute Force Approach

The most straightforward solution is to generate every permutation of numbers from 1 to n, then check whether each permutation satisfies the beautiful arrangement condition.

For each permutation:

  1. Iterate through every index i.
  2. Check whether:
  • perm[i] % i == 0, or
  • i % perm[i] == 0
  1. If all positions satisfy the condition, increment the answer.

This approach is correct because it exhaustively examines every possible arrangement and counts exactly those that satisfy the rules.

However, the runtime is prohibitively expensive. There are n! permutations, and each permutation requires O(n) validation work.

For n = 15, this becomes completely infeasible.

Optimized Backtracking with Bitmasking

The key observation is that many partial permutations become invalid very early.

Instead of generating complete permutations first, we can build the arrangement position by position:

  • At position pos, only try numbers that satisfy the divisibility condition for that position.
  • Skip numbers that are already used.
  • Backtrack immediately when no valid choices remain.

This dramatically reduces the search space.

We can optimize further using a bitmask:

  • Each bit represents whether a number has already been used.
  • Bit operations are extremely fast.
  • The recursion state becomes compact and efficient.

Because n <= 15, a 15-bit integer is sufficient to represent all usage states.

We can also memoize states if desired, but even standard backtracking with pruning performs very well for this problem.

Approach Time Complexity Space Complexity Notes
Brute Force O(n! × n) O(n) Generates all permutations and validates each
Optimal O(n × 2^n) approximately O(2^n) Backtracking with pruning and bitmask DP

Algorithm Walkthrough

Optimal Backtracking + Bitmask Algorithm

  1. Start with position 1.

We build the arrangement incrementally. At each recursive step, we decide which number to place at the current position. 2. Maintain a bitmask representing used numbers.

If bit k is set, then number k + 1 has already been placed somewhere in the arrangement. 3. For the current position pos, iterate through all candidate numbers from 1 to n.

Each number is checked for two conditions:

  • It has not been used yet.
  • It satisfies:

$$num % pos == 0 \quad \text{or} \quad pos % num == 0$$ 4. If a number is valid:

  • Mark it as used in the bitmask.
  • Recursively solve for pos + 1.
  1. When pos > n, a complete valid arrangement has been constructed.

Return 1 to count this arrangement. 6. Sum the counts returned from all recursive branches. 7. Use memoization to avoid recomputing states.

Since the state is fully determined by:

  • Current position
  • Current bitmask

we can cache results for repeated states.

Why it works

The algorithm systematically explores every valid arrangement while pruning invalid partial configurations immediately.

At every recursive step, only numbers satisfying the divisibility rule are considered. Since each number is used exactly once and every valid branch is explored, the algorithm counts all beautiful arrangements exactly once.

Memoization guarantees that identical states are computed only once, which reduces exponential recomputation.

Python Solution

class Solution:
    def countArrangement(self, n: int) -> int:
        memo = {}

        def backtrack(position: int, used_mask: int) -> int:
            if position > n:
                return 1

            if (position, used_mask) in memo:
                return memo[(position, used_mask)]

            total = 0

            for num in range(1, n + 1):
                bit = 1 << (num - 1)

                # Skip already used numbers
                if used_mask & bit:
                    continue

                # Check beautiful arrangement condition
                if num % position == 0 or position % num == 0:
                    total += backtrack(
                        position + 1,
                        used_mask | bit
                    )

            memo[(position, used_mask)] = total
            return total

        return backtrack(1, 0)

The implementation follows the recursive strategy described earlier.

The backtrack function represents the number of valid arrangements that can be formed starting from a particular position and usage state.

The base case occurs when position > n. This means all positions have been filled successfully, so we return 1 to count one valid arrangement.

The used_mask integer tracks which numbers are already placed in the permutation. Bit operations allow constant-time checks and updates.

For every recursive call:

  • We iterate through numbers 1 to n.
  • Skip numbers already used.
  • Check whether the divisibility condition holds.
  • Recurse with the updated mask.

Memoization stores previously computed states to avoid redundant work. Since many recursive paths reach the same (position, used_mask) pair, caching significantly improves performance.

Go Solution

func countArrangement(n int) int {
    memo := make(map[[2]int]int)

    var backtrack func(position int, usedMask int) int

    backtrack = func(position int, usedMask int) int {
        if position > n {
            return 1
        }

        key := [2]int{position, usedMask}

        if value, exists := memo[key]; exists {
            return value
        }

        total := 0

        for num := 1; num <= n; num++ {
            bit := 1 << (num - 1)

            // Skip already used numbers
            if usedMask&bit != 0 {
                continue
            }

            // Check beautiful arrangement condition
            if num%position == 0 || position%num == 0 {
                total += backtrack(
                    position+1,
                    usedMask|bit,
                )
            }
        }

        memo[key] = total
        return total
    }

    return backtrack(1, 0)
}

The Go implementation mirrors the Python solution closely.

Instead of Python tuples for memoization keys, Go uses a fixed-size array [2]int containing:

  • Current position
  • Current bitmask

Go does not have Python's automatic memoization structures, so we explicitly use a map.

Bit operations behave similarly in both languages, and integer overflow is not a concern because the number of beautiful arrangements for n <= 15 comfortably fits inside Go's int.

Worked Examples

Example 1

Input: n = 2

We must count all valid arrangements of [1,2].

Possible permutations:

Permutation Position 1 Position 2 Valid
[1,2] 1 % 1 == 0 2 % 2 == 0 Yes
[2,1] 2 % 1 == 0 2 % 1 == 0 Yes

Answer:

2

Recursive Trace

Step Position Used Mask Candidate Valid Action
1 1 00 1 Yes Recurse
2 2 01 2 Yes Recurse
3 3 11 - Complete Count = 1
4 1 00 2 Yes Recurse
5 2 10 1 Yes Recurse
6 3 11 - Complete Count = 2

Final answer:

2

Example 2

Input: n = 1

Only one arrangement exists:

[1]

Check:

Position Value Condition
1 1 1 % 1 == 0

Valid arrangement count:

1

Recursive Trace

Step Position Used Mask Candidate Valid Action
1 1 0 1 Yes Recurse
2 2 1 - Complete Count = 1

Complexity Analysis

Measure Complexity Explanation
Time O(n × 2^n) approximately Each bitmask state is processed once
Space O(2^n) Memoization table stores states

The total number of possible bitmask states is 2^n. For each state, we may iterate through up to n candidate numbers.

Therefore, the runtime is approximately:

$$O(n \times 2^n)$$

This is dramatically better than factorial complexity.

The memoization table stores one entry per reachable state, requiring O(2^n) memory.

The recursion stack depth is at most n.

Test Cases

sol = Solution()

assert sol.countArrangement(1) == 1  # Smallest input
assert sol.countArrangement(2) == 2  # Example case
assert sol.countArrangement(3) == 3  # Small branching case
assert sol.countArrangement(4) == 8  # More combinations
assert sol.countArrangement(5) == 10  # Medium input
assert sol.countArrangement(6) == 36  # Larger branching
assert sol.countArrangement(7) == 41  # Tests pruning efficiency
assert sol.countArrangement(8) == 132  # Larger state space
assert sol.countArrangement(9) == 250  # Stress recursion
assert sol.countArrangement(10) == 700  # Significant DP usage
assert sol.countArrangement(15) == 24679  # Maximum constraint
Test Why
n = 1 Smallest possible input
n = 2 Verifies sample case
n = 3 Tests simple recursive branching
n = 4 Confirms multiple valid permutations
n = 5 Medium-sized search space
n = 6 Validates pruning efficiency
n = 7 Tests increasing DP reuse
n = 8 Larger bitmask state space
n = 9 Ensures recursion correctness
n = 10 Tests memoization performance
n = 15 Maximum allowed constraint

Edge Cases

Edge Case 1: Smallest Input

When n = 1, there is only one possible arrangement: [1].

A buggy implementation might mishandle the recursion base case and return 0 instead of 1.

This implementation correctly handles the case because when position > n, it returns 1, indicating one valid completed arrangement.

Edge Case 2: Reusing Numbers

A common mistake is forgetting to track which numbers are already used.

For example, if n = 3, an incorrect implementation could generate invalid arrangements like [1,1,2].

The bitmask guarantees uniqueness because each number's bit is checked before selection.

Edge Case 3: Incorrect Divisibility Direction

Another common bug is checking only:

num % position == 0

while forgetting the second condition:

position % num == 0

Both directions are necessary.

For example:

  • At position 2, number 1 is valid because:

$$2 % 1 == 0$$

even though:

$$1 % 2 \ne 0$$

The implementation explicitly checks both conditions.

Edge Case 4: Large Input Near Constraint Limit

For n = 15, the search space is enormous without pruning or memoization.

A naive factorial solution would timeout badly.

The memoized bitmask solution efficiently reduces repeated computation and comfortably handles the maximum constraint.